堆以及堆排序

浏览数：17 / 时间：2015年06月08日

1. 堆

　　二叉堆是一个数组，它可以被看成一个近似的完全二叉树。

　　二叉堆有两种形式:最大堆和最小堆。在最大堆中，父节点的值总是大于等于任何一个子节点的值。因此，堆中的最大元素放在根节点中，并且在任一子树中，该字数包含的所有节点的值都不大于该子树根节点的值。最小堆是指父节点的值总是小于或等于任一子节点的值。

技术分享

　　在堆排序算法中，我们使用最大堆。最小堆通常用于构造优先队列。

2.堆的存储

　　一般都用数组来表示堆。一般位置0不用来存储元素，即存储区域为A[1,...,len]。所以对于一个节点。它的父节点的下标为2/i，左孩子的下标为2*i，右孩子的节点为2*i+1.

　　如果要使用下标为0的位置，那么父节点的下标就为(i-1)/2。它的左右子节点下标为2*i+1和2*i+2。

　　本文中将不使用0位置。

3. 向下调整

　　向下调整是为了维护堆的性质。它的输入为数组A和下标i。它首先看该节点是否大于其左右子节点的值，若不是，将左右子节点中较大值与之交换。交换后可能会破坏下一级的堆，于是继续采用上述方法构造下一级的堆，直到该节点为根的子结构成堆为止。时间复杂度为O(lgn)

 1 void AdjustDown(ElemType A[], int k, int heap_size) {
 2     int child;
 3     ElemType tmp = A[i];
 4 
 5     for (int i = k << 1; i <= heap_size; i *= 2) { // 沿键值较大的子节点向下筛选
 6         if (i < heap_size && A[i + 1] > A[i]) {
 7             i++;
 8         }
 9         if (A[child] < tmp) {
10             A[k] = A[child]; //将A[child]调整到双亲的位置
11             k = i;             //修改键值,以便继续向下筛选
12         } else {
13             break;
14         }
15 
16     }
17 
18     a[k] = tmp;                //被筛选的值放入最终的位置
19  }

　　算法导论中给出的递归的方法：

 1 inline int Left(int i) {
 2     return i << 1;
 3 }
 4 
 5 inline int Right(int i) {
 6     return i << 1 + 1;
 7 }
 8 
 9 void AdjustDown(int A[], int k, int heap_size) {
10     int left_child = Left(k);
11     int right_child = Right(k);
12 
13     int largest = k;
14 
15     if (left_child <= heap_size && A[left_child] > A[largest]) {
16         largest = leftc_child;
17     }
18     if (right_child <= heap_size && A[right_child] > A[largest]) {
19         largest = right_child;
20     }
21 
22     if (largest != k) {
23         swap(A[k], A[largest]);
24         AdjustDown(A, largest, heap_size);
25     }