堆排序具有空间原址性:任何时候都只需要常数个额外的元素空间存储临时数据。
堆(heap)
(二叉)堆是一个数组,它可以被看成一棵近似的完全二叉树。除了最底层外,该数是完全充满的,而且是从左边向右填充。(从数组上表示就是父节点总是在它的孩子节点的左边。)
性质:二叉堆可以分为最大堆和最小堆。
最大堆:除了根节点以外的所有结点i都要满足:A[PARENT(i)]>=A[i]。(堆排序算法)
- 也就是说某个结点的值至多与其父节点一样大。堆中的最大元素存放在根节点中。
- 在任一子树中,该子树所包含的所有结点的值都不大于该子树根节点的值。
最小堆:除了根节点以外的所有结点i都要满足:A[PARENT(i)]<=A[i]。(通常用于构造优先队列)
- 堆中的最小元素存放在根节点中。
相关问题:
1)高度为h的堆中,元素个数最多和最少分别为多少?
堆为一个近似完全二叉树(除了最底层),它有个元素(完全情况下),个元素(最底层只有一个元素,其他层完全)。
2)证:含n个元素的堆的高度为[lgn]。
,
3)一个已经排好序的数组是一个最小堆吗?
有序的递增数组是最小堆,递减的有序数组是最大堆。
用数组实现堆
用从上到下,从左到右的方式记录堆的数据。为了方便,在这种数组从1到n的位置上存放堆元素,留下H[0]。要么让它空着,要么在其中放置一个限位器,它的值大于堆中的任何一个元素。
- 父母节点的键将会位于数组的前个位置中,而叶子结点的键将会将会位于数组的后个位置中。也就是叶结点的下标分别为,,...,。
- 在数组中,对于一个位于父母位置的键来说,它的子女将会位于和,相应地,对于一个位于的键来说,它的父母将会位于。
把堆定义成一个数组H[1,...,n],其中对于数组前半部分中,每个位置i上的元素,总是大于等于位置2i和2i+1的元素。
对于,
把堆理解为二叉树可以理解其隐含思想,对于实际实现来说,使用数组更为高效。
维护堆的性质
Max-HEPAIFY过程
首先来一个直观的认识。如图,初始状态,结点i=2处,A[2]违背了最大堆性质,因为其值不大于它的孩子。在(b)中,通过交换A[2]和A[4]的值,结点2恢复了最大堆的性质。但导致结点4违背最大堆性质。此时i=4,递归调用Max-HEPAIFY函数,通过交换A[4]与A[9]的值,结点4的最大堆性质的到了恢复。再次递归调用Max-HEPAIFY函数,无数据再需要交换。
伪代码:
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
#define LEFT(i) i<<1 #define RIGHT(i) (i<<1)+1 #define PARENT(i) i>>1 void swap(int *a,int *b){ int temp=*a; *a=*b; *b=temp; } int MAX_HEAPFIY(int *A,int i,int heap_size){ int result=0; int largest=0; int l=LEFT(i); int r=RIGHT(i); if (l<=heap_size && A[l]>A[i]) largest=l; else largest=i; if(r<=heap_size && A[r]>A[largest]) largest=r; if(largest!=i) swap(A+i,A+largest); else { result=1; return result; } if(result!=1){ MAX_HEAPFIY(A,largest,heap_size); } } int _tmain(int argc, _TCHAR* argv[]){ int A[11]={1000,16,4,10,14,7,9,3,2,8,1}; int i=MAX_HEAPFIY(A,2,10); for(int i=0;i<11;i++){ cout<<A[i]<<","; } cout<<endl; return 0; } |
讨论:对于一棵以i为根结点,大小为n的子树,MAX_HEAPIFY的时间代价包括:调整A[i]和A[LEFT(i)]、A[RIGHT(i)]的关系的时间代价,加上在一棵以i的一个孩子为根结点的子树上运行MAX_HEAPIFY的时间代价(假设递归调用发生)。这里有一个重要结论,每个孩子的子树的大小至多为2n/3(证明如下)。那么可以得到如下递归式:
递归式的解为。也就是说对于一个树高为h的结点来说,MAX_HEAPIFY的时间复杂度为。
主定理:(算法导论结论)
相关问题:
1)证明:对于一个大小为n的堆,MAX_HEAPIFY的最坏情况运行时间为。
证:当根结点的值小于其左右子树中的每一个值,显然MAX_HEAPIFY会被递归调用直到其到达叶结点。要让根结点到叶节点的路径上的每个结点都会递归调用MAX_HEAPIFY,显然是要让其在左子树上进行递归。也就是说左子树中的值要大于右子树的节点,所以在根节点放0,然后其他结点全部放1,可以实现这种最坏运行情况。这种情况下,MAX_HEAPIFY会被调用h次(h为堆高度)。we have
a case in which MAX-HEAPIFY’s running time is , its worst-case running
time is .
1 2 |
高度为1的那层(倒数第2层)虽然有4个 节点,然而只有2个节点有孩子,也就是说右边的另外两个应该算作高度为0 |
1 2 3 4 5 6 7 |
当堆是满二叉树时: 最底层的元素个数为ceiling(n/2)个,这层高度为0; 倒数第二层元素个数为ceiling(n/4)个,高度为1; 倒数第三层元素个数为ceiling(n/8)个,高度为2; 如此类推,高度为h的,在倒数第h + 1层,元素个数为ceiling(n / 2^(h + 1))。 若堆不是满二叉树,这个数目则总少于ceiling(n / 2^(h + 1))了。 |
2)一棵以节点i为根的、大小为n的子树上,i节点的子树大小至多为2n/3(最坏情况:底层恰好半满的时候)?
讨论完全二叉树,规定总size为n,要求根的左子树的最大size。(由于右子树size总是<=左子树size)。观察最底层节点数目为0, 1, 2...的情况,显然半满的时候左子树达到了最大 。以下求此时左子树的大小:
1 2 |
设底层半满时节点数为x,则再加x个节点,就是满树:n + x = 2x * 2 - 1 = 满树size 可得n = 3x - 1满树时,左子树节点数 = (满树size - 1) / 2 = 2x -1 ~= 2n / 3 |
建堆
用自底向上的方法利用过程MAX_HEAPIFY把一个大小为n=A.length的数组A[1,...,n]转换为最大堆。子数组中的元素为叶结点。对树中的其他结点都调用一次MAX_HEAPIFY。
伪代码:
1 2 3 |
for(int i=11/2;i>=1;i--){ int result=MAX_HEAPFIY(A,i,10); } |
重要结论:BUILD-MAX-HEAP的时间复杂度为。也就是说,在线性时间内,把一个无序数组构造成一个最大堆。
堆排序(HEAPSORT)
有了上面的背景知识,我们就可以快速的学习堆排序的思想了。首先还是给出一个示意图,来直观的了解堆排序的过程。
伪代码:
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
int _tmain(int argc, _TCHAR* argv[]){ int A[11]={1000,16,4,10,14,7,9,3,2,8,1}; int heap_size=10; for(int i=11/2;i>=1;i--){ int result=MAX_HEAPFIY(A,i,heap_size); } for(int i=10;i>=2;i--){ swap(A+1,A+i); heap_size=heap_size-1; MAX_HEAPFIY(A,1,heap_size); } for(int i=0;i<11;i++){ cout<<A[i]<<","; } return 0; } |
时间复杂度分析:BUILD-MAX-HEAP的时间复杂度为,而n-1次 调用MAX-HEAPIFY的时间为。所以HEAPSORT的时间复杂度为
相关习题:
1)对于一个按升序排序的包含n个元素的有序数组来说,HEAPSORT的时间复杂度是多少?如果A是降序呢?
2)
参考资料:
1)http://clrs.skanev.com/
2)https://github.com/gzc/CLRS