首页 > 代码库 > 【算法导论】学习笔记——第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 }