首页 > 代码库 > 【算法导论】学习笔记——第6章 堆排序

【算法导论】学习笔记——第6章 堆排序

堆这个数据结构应用非常广泛,数字图像处理的算法里也见过。似乎记得以前老师上课说需要用树结构实现堆排序,看了一下算法导论才明白其精髓。堆虽然是一棵树,但显然没必要非得用树结构实现堆排序。堆排序的性质很好,算法时间复杂度为O(nlgn)。

1. 堆排序的简要说明。
二叉堆可以分为两种形式:最大堆和最小堆。
在最大堆中,最大堆性质是指除了根以外的所有结点i都要满足:
  A[PARENT(i)] >= A[i];
在最小堆中,最小堆性质是指除了根以外的所有结点i都要满足:
  A[PARENT(i)] <= A[i]。
关于堆排序的算法实现,有如下基本过程需要了解:
(1)MAX_HEAPIFY过程:其时间复杂度为O(lgn),它是维护最大堆性质的关键;
(2)BUILD_MAX_HEAP过程:具有线性时间复杂度,功能是从无序的输入数据数组中构造一个最大堆;
(3)HEAPSORT过程,其时间复杂度为O(nlgn),功能是对一个数组进行原址排序;
(4)MAX_HEAP_INSERT、MAX_EXTRACT_MAX、HEAP_INCREASE_KEY和HEAP_MAXIMUM过程:时间复杂度为   O(lgn),功能是利用堆实现一个优先队列。
堆结构定义如下:

 1 #define PARENT(i)   (i>>1) 2 #define LEFT(i)     (i<<1) 3 #define RIGHT(i)    (i<<1|1) 4 #define MAXN        105 5  6 typedef struct { 7     int buf[MAXN]; 8     int length; 9     int size;10 } Heap_t;


2. 维护堆的性质。
MAX_HEAPIFY是维护最大堆性质的重要过程。代码实现如下:

 1 void MAX_Heapify(Heap_t *A, int i) { 2     int l = LEFT(i); 3     int r = RIGHT(i); 4     int largest; 5     int tmp; 6  7     if (l<=A->size && A->buf[l]>A->buf[i]) 8         largest = l; 9     else10         largest = i;11     if (r<=A->size && A->buf[r]>A->buf[largest])12         largest = r;13     if (largest != i) {14         tmp = A->buf[i];15         A->buf[i] = A->buf[largest];16         A->buf[largest] = tmp;17         MAX_Heapify(A, largest);18     }19 }

也可采用非递归形式实现,代码如下:

 1 void MAX_Heapify(Heap_t *A, int i) { 2     int l, r; 3     int largest; 4     int tmp; 5  6     while (i+i <= A->size) { 7         l = LEFT(i); 8         r = RIGHT(i); 9         if (l<=A->size && A->buf[l]>A->buf[i])10             largest = l;11         else12             largest = i;13         if (r<=A->size && A->buf[r]>A->buf[largest])14             largest = r;15         if (largest != i) {16             tmp = A->buf[i];17             A->buf[i] = A->buf[largest];18             A->buf[largest] = tmp;19             i = largest;20         } else {21             break;22         }23     }24 }

3. 建堆
BUILD_MAX_HEAPIFY描述了建堆的主要过程,建堆时仅需针对非叶子结点调用MAX_HEAPIFY过程。建堆的时间复杂度为O(n)。

1 void Build_MAX_Heap(Heap_t *A) {2     int i;3 4     A->size = A->length;5     for (i=A->length>>1; i>=1; --i) {6         MAX_Heapify(A, i);7     }8 }

有关6.3-3的证明,对于任何包含n个元素的堆中,至多有ceil(n/2^(h+1))个高度为h的点。
证明:
(1)先证叶子结点(高度h=0)满足该结论,即至多有ceil(n/2^1)个叶子结点。令叶子结点的下标为i,i属于[1,n],
则2*i>n,i<=n,即n/2 < i <= n。因为i为整数,因此floor(n/2) < i <= n,所以N(h=0) <= floor(n) - floor(floor(n/2)) (《具体数学》3.12),因此N(h=0) <= n - floor(n/2),又因为floor(n/2)+ceil(n/2) = n,所以N(h=0) <= ceil(n/2),余下点的数目n - N(h=0) >= floor(n/2);
(2)假设高度为k-1的子树均满足上述结论,采用数学归纳法证明高度为k的子树满足上述结论。
因此,易知k<=H(H为树的高度,H=floor(lgn))。假设,高度为k的点下标为i。因为N(h=0)时,N(h=0)=ceil(n/2);将原叶子结点全部去掉,子数的高度势必均减1,因此N(h=k) = N(hh = k-1) <= ceil(nn/2^h),nn = n - ceil(n/2) = floor(n/2),因此N(h=k) = <= ceil(floor(n/2)/2^h),因为floor(n/2) <= n/2,因此N(h=k) <= ceil(n/2/2^h),所以N(h = k) <= ceil(n/2^(h+1))。

4. 堆排序算法。
初始时,堆排序算法利用BUILD_MAX_HEAPIFY过程建立初始的最大堆,此时,最大元素一定处在根结点,交换根结点与A[n],并重新建立堆(此时堆大小需要减1),我们即将最大元素置于数组最末处进行孤立。不断重复此过程,直至仅有两个元素的堆为止,即可得到有序的数组。代码实现如下:

 1 void HeapSort(Heap_t *A) { 2     int i, tmp; 3  4     Build_MAX_Heap(A); 5     for (i=A->length; i>=2; --i) { 6         tmp = A->buf[1]; 7         A->buf[1] = A->buf[i]; 8         A->buf[i] = tmp; 9         --A->size;10         MAX_Heapify(A, 1);11     }12 }


5. 优先队列。
优先队列是堆这种数据结构的典型应用。优先队列是一种用来维护由一组元素构成的集合S的数据结构,每个元素都有一个相关的值,称为关键字,一个优先队列支持如下操作:
(1)INSERT(S, x):把元素x插入S中;
(2)MAXIMUM(S):返回S中具有最大关键字的元素;
(3)EXTRACT_MAX(S):去掉并返回S中的具有最大关键字的元素;
(4)INCREASE(S, x, k):将元素x的关键字值增加到k,假设k的值不小于x的原始关键字值。
代码实现:

 1 int Heap_Maximum(Heap_t *A) { 2     return A->buf[1]; 3 } 4  5 int Heap_Extract_MAX(Heap_t *A) { 6     int max; 7  8     if (A->size < 1) { 9         printf("heap underflow.\n");10         return -1;11     }12     max = A[1];13     A[1] = A[A->size];14     --A->size;15     MAX_Heapify(A, 1);16 17     return max;18 }19 20 void Heap_Increase_Key(Heap_t *A, int i, int key) {21     int tmp;22 23     if (key < A->buf[i]) {24         printf("new key is smaller than current key.\n");25         return ;26     }27     A[i] = key;28     while (i>1 && A->buf[PARENT(i)]<A->buf[i]) {29         tmp = A->buf[i];30         A->buf[i] = A->buf[PARENT(i)];31         A->buf[PARENT(i)] = tmp;32         i = PARENT(i);33     }34 }35 36 void MAX_Heap_Insert(Heap_t *A, key) {37     ++A->size;38     A[A->size] = NINF;  // NINF: negative infinite39     Heap_Increase_Key(A, A->size, key);40 }

6.5-6问题解答,即简单优化Heap_Increase_Key函数,代码实现如下:

 1 void Heap_Increase_Key(Heap_t *A, int i, int key) { 2     if (key < A->buf[i]) { 3         printf("new key is smaller than current key.\n"); 4         return ; 5     } 6  7     while (i>1 && A->buf[PARENT(i)]<key) { 8         A->buf[i] = A->buf[PARENT(i)]; 9         i = PARENT(i);10     }11     A[i] = key;12 }