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

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

2024-07-18 11:43:58   223人阅读

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

 


联系
我们