rambo

排序算法四（堆排序）

2015年8月1日 Data Strcuture 0 Comments

堆排序具有空间原址性：任何时候都只需要常数个额外的元素空间存储临时数据。

堆(heap)

（二叉）堆是一个数组，它可以被看成一棵近似的完全二叉树。除了最底层外，该数是完全充满的，而且是从左边向右填充。（从数组上表示就是父节点总是在它的孩子节点的左边。）

性质：二叉堆可以分为最大堆和最小堆。

最大堆：除了根节点以外的所有结点i都要满足：A[PARENT(i)]>=A[i]。（堆排序算法）

  • 也就是说某个结点的值至多与其父节点一样大。堆中的最大元素存放在根节点中。
  • 在任一子树中，该子树所包含的所有结点的值都不大于该子树根节点的值。

最小堆：除了根节点以外的所有结点i都要满足：A[PARENT(i)]<=A[i]。（通常用于构造优先队列）

  • 堆中的最小元素存放在根节点中。

相关问题：

1）高度为h的堆中，元素个数最多和最少分别为多少？
堆为一个近似完全二叉树（除了最底层），它有2^{h+1}-1个元素（完全情况下），2^{h}-1+1个元素（最底层只有一个元素，其他层完全）。
2）证：含n个元素的堆的高度为[lgn]。
2^{h} \leq n \leq 2^{h+1}-1<2^{h+1}，h \leq lgn <h+1
3)一个已经排好序的数组是一个最小堆吗？
有序的递增数组是最小堆，递减的有序数组是最大堆。

用数组实现堆

QQ截图20150906131535

用从上到下，从左到右的方式记录堆的数据。为了方便，在这种数组从1到n的位置上存放堆元素，留下H[0]。要么让它空着，要么在其中放置一个限位器，它的值大于堆中的任何一个元素。

  • 父母节点的键将会位于数组的前\lfloor n/2 \rfloor个位置中，而叶子结点的键将会将会位于数组的后\lceil n/2\rceil个位置中。也就是叶结点的下标分别为\lfloor n/2 \rfloor+1，\lfloor n/2 \rfloor+2，...， n。
  • 在数组中，对于一个位于父母位置i(1 \leq i \leq\lfloor n/2 \rfloor的键来说，它的子女将会位于2i和2i+1，相应地，对于一个位于i(2 \leq i \leq 2的键来说，它的父母将会位于\lfloor i/2 \rfloor。

把堆定义成一个数组H[1,...,n]，其中对于数组前半部分中，每个位置i上的元素，总是大于等于位置2i和2i+1的元素。

对于i(1 \leq i \leq\lfloor n/2 \rfloor，H[i] \ge max\{H[2i],H[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函数，无数据再需要交换。

QQ截图20150801151617

伪代码：

QQ截图20150801152359

代码：

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)]的关系的时间代价\Theta(1)，加上在一棵以i的一个孩子为根结点的子树上运行MAX_HEAPIFY的时间代价（假设递归调用发生）。这里有一个重要结论，每个孩子的子树的大小至多为2n/3（证明如下）。那么可以得到如下递归式：

T(n)\leq T(2n/3)+\Theta(1)

递归式的解为T(n)=\rm O(lgn)。也就是说对于一个树高为h的结点来说，MAX_HEAPIFY的时间复杂度为\rm O(h)。

主定理：（算法导论结论）

QQ截图20150801201537

相关问题：

1）证明：对于一个大小为n的堆，MAX_HEAPIFY的最坏情况运行时间为\Omega(lgn)。

证：当根结点的值小于其左右子树中的每一个值，显然MAX_HEAPIFY会被递归调用直到其到达叶结点。要让根结点到叶节点的路径上的每个结点都会递归调用MAX_HEAPIFY，显然是要让其在左子树上进行递归。也就是说左子树中的值要大于右子树的节点，所以在根节点放0，然后其他结点全部放1，可以实现这种最坏运行情况。这种情况下，MAX_HEAPIFY会被调用h次（h为堆高度）。we have
a case in which MAX-HEAPIFY’s running time is \Theta(lgn), its worst-case running
time is \Omega(lgn).

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]转换为最大堆。子数组A(\lfloor n/2 \rfloor+1,...,n)中的元素为叶结点。对树中的其他结点都调用一次MAX_HEAPIFY。

伪代码：

QQ截图20150801203436

QQ截图20150801203535

1
2
3
for(int i=11/2;i>=1;i--){
int result=MAX_HEAPFIY(A,i,10);
}

QQ截图20150801203800

 

重要结论：BUILD-MAX-HEAP的时间复杂度为\rm O(n)。也就是说，在线性时间内，把一个无序数组构造成一个最大堆。

  堆排序（HEAPSORT）

有了上面的背景知识，我们就可以快速的学习堆排序的思想了。首先还是给出一个示意图，来直观的了解堆排序的过程。

QQ截图20150801204915

 

伪代码：

QQ截图20150801204959

代码：

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;
}

QQ截图20150801205621

时间复杂度分析：BUILD-MAX-HEAP的时间复杂度为\rm O(n)，而n-1次 调用MAX-HEAPIFY的时间为\rm O(lgn)。所以HEAPSORT的时间复杂度为\rm O(nlgn)

相关习题：

1）对于一个按升序排序的包含n个元素的有序数组来说，HEAPSORT的时间复杂度是多少？如果A是降序呢？

QQ截图20150801205955

 

2)

QQ截图20150801212539

 

参考资料：

1）http://clrs.skanev.com/

2)https://github.com/gzc/CLRS

QQ截图20150801213358

,