1 /*-----------Heap-Sort implemented in C------------------*/ 2 3 #include <stdio.h> 4 #include <stdlib.h> 5 6 inline int left(int i) 7 { 8 //C语言中下标从0开始 9 return (i<<1)+1; 10 } 11 inline int right(int i) 12 { 13 return (i<<1)+2; 14 } 15 inline int parent(int i) 16 { 17 return (i-1)>>1; 18 } 19 void swap(int* A,int i,int j) 20 { 21 int temp=A[i]; 22 A[i]=A[j]; 23 A[j]=temp; 24 } 25 void max_heaptify(int* A,int i,int n) 26 { 27 int l=left(i); 28 int r=right(i); 29 int largest; 30 if(l<n && A[l]>A[i]) 31 largest=l; 32 else 33 largest=i; 34 if(r<n && A[r]>A[largest]) 35 largest=r; 36 if(largest != i) 37 { 38 swap(A,i,largest); 39 max_heaptify(A,largest,n); 40 } 41 } 42 void build_max_heap(int* A,int n) 43 { 44 //这里的下标计算也要小心 45 int i=(n-2)/2; 46 for(;i>=0;--i) 47 { 48 max_heaptify(A,i,n); 49 } 50 } 51 void heap_sort(int* A,int i,int n) 52 { 53 build_max_heap(A,n); 54 while(n>0) 55 { 56 swap(A,0,n-1); 57 --n; 58 max_heaptify(A,0,n); 59 } 60 61 } 62 //所有排序的主函数保持形式上的一致性 63 int main() 64 { 65 int A[30]; 66 int i=0; 67 printf("Original:\n"); 68 for (;i<30;i++) 69 { 70 A[i]=rand(); 71 printf("%d\t",A[i]); 72 } 73 heap_sort(A,0,30); 74 printf("\nRearrange:\n"); 75 for(i=0;i<30;++i) 76 { 77 printf("%d\t",A[i]); 78 } 79 }
1 inline int heap_maximum(int* A) 2 { 3 return A[0]; 4 } 5 int heap_extract_max(int* A,int size) 6 { 7 if(size<=0) exit(-1); 8 int max=A[0]; 9 swap(A,0,size-1); 10 --size; 11 max_heaptify(A,0,size); 12 return max; 13 } 14 void heap_increase_key(int* A,int i,int key,int size) 15 { 16 if(i>=size)exit(-1); 17 if(A[i]>key)exit(-2); 18 A[i]=key; 19 int j; 20 while((j=parent(i))>=0 && A[i]>j) 21 { 22 swap(A,i,j); 23 i=j; 24 } 25 } 26 void heap_insert(int* A,int value,int size) 27 { 28 //overflow may happen here 29 size+=1; 30 if(size>=heap_size)exit(-3); 31 A[size-1]=INT_MIN; 32 heap_increase_key(A,size-1,value,size); 33 }
exercises：
6.1-1 $2^{h+1} \ge n \ge 2^h$，很简单，每层最多有$2^h$个元素，最底层最少有1个元素。
6.1-2 对上式求对数可得。
6.1-3 根据最大堆的定义易推知。
6.1-4 叶子结点。
6.1-5 不是，举例可证。
6.1-6 不是，画出来可以看出来，6和7的顺序反过来才是。
6.1-7 主要根据度为2的结点是度为0的结点个数+1这个结论。
6.2-2 Min-Heapify(A,i)
l ← LEFT(i)
r ← RIGHT(i)
if l <heap-size(A) and A[l]<A[i]
then smallest ← l
else smallest ← i
if r<heap-size(A) and A[r]<A[smallest]
then smallest ← r
if i ≠ smallest
then swap A[i]↔A[smallest]
Min-Heaptify(A,smallest)
运行时间一致…都是$\Theta(lgn)$
6.2-3 无效果
6.2-4 对叶子结点使用，无效果
6.2-5 将第10行以后改成
while l ≤ heap-size(A) and r ≤ heap-size(A)
do if A[l] > A[i]
then largest ← l
else largest ← i
if A[r] > A[largest]
then largest ← r
if i≠ largest
then swap A[i]↔A[largest]
i ← largest
即可
6.2-6 其实就是从根节点到叶节点全部都要执行一次max-heapify，故时间就是树的深度$\Theta(lgn)$
6.3-2 只有递减才能保证每次交换顺序后，下标在被交换元素后面的堆数据仍保持最大堆性质。
6.3-3 此题注意一点：高度为h的结点，深度是H-h。H是树的总高度。
6.4-3 都是O(nlgn)
6.4-4 最坏情况同max-heaptify的最坏情况。
6.5-3 Min-Heapify的伪代码见6.2-2
Heap-Minimum(A)
return A[1]
Heap-Extract-Min(A)
if heap-size(A)<1
then error "heap underflow"
min ← A[1]
A[1] ← A[heap-size(A)]
heap-size(A) ← heap-size(A)-1
Min-Heapify(A,1)
return min
Heap-Decrease-Key(A,i,key)
if A[i]<key
error "new key is bigger then current key"
A[i]=key
while i>1 and A[i]<A[parent[i]]
do swap A[i]↔A[parent[i]
i ← parent[i]
Min-Heap-Insert(A,key)
heap-size[A] ← heap-size[A]+1
A[heap-size[A]] ← +∞
Heap-Decrease-Key(A,heap-size[A],key)
6.5-4 设为负无穷大可以保证增加的元素不违反最大堆的特性，从而保证Increase Key的函数能够正常返回
6.5-6 队列是先进先出，可以使用最小堆，先进的元素具有最低的key，后面的递增；
堆栈是先进后出，使用最大堆，先进的元素仍然具有最低的key，后面的递增。
6.5-7 Heap-Delete(A,i)
swap A[i] ↔ A[heap-size[A]]
heap-size(A) ← heap-size(A)-1
Max-Heapify(A,i)
6.5-8 提取k路链表的根指针，放入数组A，将根指针指向的value作为key对数组进行（最小）堆排序。然后提取A[1]，作为排序后的首元素，将A[1]替换为原来的元素指向的链表下一个元素（如果为空，则将数组最后一个元素放在此位置，k-1），再Min-Heapify(A,1)。如此循环直到n个元素全部排序完毕。
Min-Heapify的时间为$\Theta(k)$，循环n次，故中的时间为O(nlgk)。
problems：
6-1 a>不是一样的，可以例证。有些树的兄弟位置会变化；
b>略
6-2 b>$log_bn$
c>不过是比较的次数由2次变成了d次，所以复杂度也增加到O($d \times log_bn$)，忽略常数因子，与b相同。
d>基本无变化，复杂度同上
e>同上
6-3 与堆相似，不同的是比较的对象是元素的上下左右四个元素，其中上左相当于最小堆的parent，下右类似于左右孩子。
注意d中插入时元素要与上、左中较大的元素交换位置，这样才能保持Young氏矩阵的性质。
f中似乎可以通过二分和矩阵分块的思想每次减少1/4的问题，这样可以超过题中要求的线性算法。