算法导论第6章堆排序答案

╰+哭是因爲堅強的太久メ 2022-05-15 11:40 220阅读 0赞

# 一、概念 #

## 1.堆的定义与性质 ##

（1）堆是一种数组对象

（2）堆可以被视频一棵完全二叉树，二叉树的层次遍历结果与数组元素的顺序对应，树根为A\[1\]。对于数组中第i个元素，具体计算如下

PARENT(i) return i/2

LEFT(i) return 2i

RIGHT(i) return 2i+1

（3）一个最大堆对应的树，每一个结点p，若其孩子存在，则key\[p\] > key\[p->left\] && key\[p\] > key\[p->right\]

## 2.堆的结构 ##

A\[N\]：堆数组

length\[A\]：数组中元素的个数

heap-size\[A\]：存放在A中的堆的元素个数

## 3.在堆上的操作 ##

（1）MAX-HEAPIFY(A, i)

（2）BUILD-MAX-HEAP(A)

（3）HEAPSORT(A)

## 4.堆的应用 ##

优先级队列

（1）HEAP-MAXIMUM(A)

（2）HEAP-INCREASE-KEY(A, i, key)

（3）HEAP-EXTRACT-KEY(A)

（4）MAX-HEAP-INSERT(A, key)

# 二、程序 #

**\[cpp\]** [ view plain][view plain] [copy][view plain] [print][view plain] [?][view plain]

1.  //头文件   
2.  \#include <iostream>   
3.  \#include <stdio.h>    
4.  using namespace std;  
5.    
6.  //宏定义   
7.  \#define N 1000   
8.  \#define PARENT(i) (i)>>1   
9.  \#define LEFT(i) (i)<<1    
10. \#define RIGHT(i) ((i)<<1)+1   
11.   
12. class Heap  
13. \{  
14. public:  
15.     //成员变量   
16.     int A\[N+1\];  
17.     int length;  
18.     int heap\_size;  
19.     //构造与析构   
20.     Heap()\{\}  
21.     Heap(int size):length(size),heap\_size(size)\{\}  
22.     ~Heap()\{\}  
23.     //功能函数   
24.     void Max\_Heapify(int i);  
25.     void Build\_Max\_Heap();  
26.     void HeapSort();  
27.     //优先队列函数   
28.     void Heap\_Increase\_Key(int i, int key);  
29.     void Max\_Heap\_Insert(int key);  
30.     int Heap\_Maximum();  
31.     int Heap\_Extract\_Max();  
32.     void Heap\_Delete(int i);  
33.     //辅助函数   
34.     void Print();  
35. \};  
36.   
37. //使以i结点为根结点的子树成为堆，调用条件是确定i的左右子树已经是堆，时间是O(lgn)  
38. //递归方法   
39. void Heap::Max\_Heapify(int i)  
40. \{  
41.     Print();  
42.     int l = LEFT(i), r = RIGHT(i), largest;  
43.     //选择i、i的左、i的右三个结点中值最大的结点    
44.     if(l <= heap\_size && A\[l\] > A\[i\])  
45.         largest = l;  
46.     else largest = i;  
47.     if(r <= heap\_size && A\[r\] > A\[largest\])  
48.         largest = r;  
49.     //如果根最大，已经满足堆的条件，函数停止    
50.     //否则   
51.     if(largest != i)  
52.     \{  
53.         //根与值最大的结点交互   
54.         swap(A\[i\], A\[largest\]);  
55.         //交换可能破坏子树的堆，重新调整子树    
56.         Max\_Heapify(largest);  
57.     \}  
58. \}  
59.   
60. //建堆，时间是O(nlgn)   
61. void Heap::Build\_Max\_Heap()  
62. \{  
63.     heap\_size = length;  
64.     //从堆中最后一个元素开始，依次调整每个结点，使符合堆的性质    
65.     for(int i = length / 2; i >= 1; i--)  
66.         Max\_Heapify(i);  
67. \}  
68.   
69. //堆排序，时间是O(nlgn)   
70. void Heap::HeapSort()  
71. \{  
72.     //建立一个最大堆   
73.     Build\_Max\_Heap();  
74.     //每次将前i个元素构成最大堆   
75.     for(int i = length; i > 1; i--)  
76.     \{  
77.         //将前i个元素中的最大值存入到A\[i\]中    
78.         swap(A\[1\], A\[i\]);  
79.         //堆的大小减一   
80.         heap\_size--;  
81.         //只有堆顶的性质可能会被破坏    
82.         Max\_Heapify(1);  
83.     \}  
84. \}  
85.   
86. //将元素i的关键字增加到key，要求key>=A\[i\]   
87. void Heap::Heap\_Increase\_Key(int i, int key)  
88. \{  
89.     if(key < A\[i\])  
90.     \{  
91.         cout<<"new key is smaller than current key"<<endl;  
92.         exit(0);  
93.     \}  
94.     A\[i\] = key;  
95.     //跟父比较，若A\[PARENT(i)\]<A\[i\]，则交换  
96.     //若运行到某个结点时A\[PARENT(i)\]>A\[i\]，就跳出循环    
97.     while(A\[PARENT(i)\] > 0 && A\[PARENT(i)\] < A\[i\])  
98.     \{  
99.         swap(A\[PARENT(i)\], A\[i\]);  
100.         i = PARENT(i);  
101.     \}  
102. \}  
103.   
104. //把key插入到集合A中   
105. void Heap::Max\_Heap\_Insert(int key)  
106. \{  
107.     if(heap\_size == N)  
108.     \{  
109.         cout<<"heap is full"<<endl;  
110.         exit(0);  
111.     \}  
112.     heap\_size++;length++;  
113.     A\[heap\_size\] = -0x7fffffff;  
114.     Heap\_Increase\_Key(heap\_size, key);  
115. \}  
116. //返回A中最大关键字，时间O(1)   
117. int Heap::Heap\_Maximum()  
118. \{  
119.     return A\[1\];  
120. \}  
121. //去掉并返回A中最大关键字，时间O(lgn)    
122. int Heap::Heap\_Extract\_Max()  
123. \{  
124.     if(heap\_size < 1)  
125.     \{  
126.         cout<<"heap underflow"<<endl;  
127.         exit(0);  
128.     \}  
129.     //取出最大值   
130.     int max = A\[1\];  
131.     //将最后一个元素补到最大值的位置   
132.     A\[1\] = A\[heap\_size\];  
133.     heap\_size--;  
134.     //重新调整根结点   
135.     Max\_Heapify(1);  
136.     //返回最大值   
137.     return max;  
138. \}  
139. //删除堆中第i个元素   
140. void Heap::Heap\_Delete(int i)  
141. \{  
142.     if(i > heap\_size)  
143.     \{  
144.         cout<<"there's no node i"<<endl;  
145.         exit(0);  
146.     \}  
147.     //把最后一个元素补到第i个元素的位置    
148.     int key = A\[heap\_size\];  
149.     heap\_size--;  
150.     //如果新值比原A\[i\]大，则向上调整   
151.     if(key > A\[i\])  
152.         Heap\_Increase\_Key(i, key);  
153.     else//否则，向下调整  
154.     \{  
155.         A\[i\] = key;  
156.         Max\_Heapify(i);  
157.     \}  
158. \}  
159.   
160. void Heap::Print()  
161. \{  
162.     int i;  
163.     for(i = 1; i <= length; i++)  
164.     \{  
165.         if(i > 1)cout<<',';  
166.         else cout<<"==> A = \{";  
167.         cout<<A\[i\];  
168.     \}  
169.     cout<<'\}'<<endl;  
170. \}

//头文件
    #include <iostream>
    #include <stdio.h>
    using namespace std;
    
    //宏定义
    #define N 1000
    #define PARENT(i) (i)>>1
    #define LEFT(i) (i)<<1
    #define RIGHT(i) ((i)<<1)+1
    
    class Heap
    {
    public:
    	//成员变量
    	int A[N+1];
    	int length;
    	int heap_size;
    	//构造与析构
    	Heap(){}
    	Heap(int size):length(size),heap_size(size){}
    	~Heap(){}
    	//功能函数
    	void Max_Heapify(int i);
    	void Build_Max_Heap();
    	void HeapSort();
    	//优先队列函数
    	void Heap_Increase_Key(int i, int key);
    	void Max_Heap_Insert(int key);
    	int Heap_Maximum();
    	int Heap_Extract_Max();
    	void Heap_Delete(int i);
    	//辅助函数
    	void Print();
    };
    
    //使以i结点为根结点的子树成为堆，调用条件是确定i的左右子树已经是堆，时间是O(lgn)
    //递归方法
    void Heap::Max_Heapify(int i)
    {
    	Print();
    	int l = LEFT(i), r = RIGHT(i), largest;
    	//选择i、i的左、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]);
    		//交换可能破坏子树的堆，重新调整子树
    		Max_Heapify(largest);
    	}
    }
    
    //建堆，时间是O(nlgn)
    void Heap::Build_Max_Heap()
    {
    	heap_size = length;
    	//从堆中最后一个元素开始，依次调整每个结点，使符合堆的性质
    	for(int i = length / 2; i >= 1; i--)
    		Max_Heapify(i);
    }
    
    //堆排序，时间是O(nlgn)
    void Heap::HeapSort()
    {
    	//建立一个最大堆
    	Build_Max_Heap();
    	//每次将前i个元素构成最大堆
    	for(int i = length; i > 1; i--)
    	{
    		//将前i个元素中的最大值存入到A[i]中
    		swap(A[1], A[i]);
    		//堆的大小减一
    		heap_size--;
    		//只有堆顶的性质可能会被破坏
    		Max_Heapify(1);
    	}
    }
    
    //将元素i的关键字增加到key，要求key>=A[i]
    void Heap::Heap_Increase_Key(int i, int key)
    {
    	if(key < A[i])
    	{
    		cout<<"new key is smaller than current key"<<endl;
    		exit(0);
    	}
    	A[i] = key;
    	//跟父比较，若A[PARENT(i)]<A[i]，则交换
    	//若运行到某个结点时A[PARENT(i)]>A[i]，就跳出循环
    	while(A[PARENT(i)] > 0 && A[PARENT(i)] < A[i])
    	{
    		swap(A[PARENT(i)], A[i]);
    		i = PARENT(i);
    	}
    }
    
    //把key插入到集合A中
    void Heap::Max_Heap_Insert(int key)
    {
    	if(heap_size == N)
    	{
    		cout<<"heap is full"<<endl;
    		exit(0);
    	}
    	heap_size++;length++;
    	A[heap_size] = -0x7fffffff;
    	Heap_Increase_Key(heap_size, key);
    }
    //返回A中最大关键字，时间O(1)
    int Heap::Heap_Maximum()
    {
    	return A[1];
    }
    //去掉并返回A中最大关键字，时间O(lgn)
    int Heap::Heap_Extract_Max()
    {
    	if(heap_size < 1)
    	{
    		cout<<"heap underflow"<<endl;
    		exit(0);
    	}
    	//取出最大值
    	int max = A[1];
    	//将最后一个元素补到最大值的位置
    	A[1] = A[heap_size];
    	heap_size--;
    	//重新调整根结点
    	Max_Heapify(1);
    	//返回最大值
    	return max;
    }
    //删除堆中第i个元素
    void Heap::Heap_Delete(int i)
    {
    	if(i > heap_size)
    	{
    		cout<<"there's no node i"<<endl;
    		exit(0);
    	}
    	//把最后一个元素补到第i个元素的位置
    	int key = A[heap_size];
    	heap_size--;
    	//如果新值比原A[i]大，则向上调整
    	if(key > A[i])
    		Heap_Increase_Key(i, key);
    	else//否则，向下调整
    	{
    		A[i] = key;
    		Max_Heapify(i);
    	}
    }
    
    void Heap::Print()
    {
    	int i;
    	for(i = 1; i <= length; i++)
    	{
    		if(i > 1)cout<<',';
    		else cout<<"==> A = {";
    		cout<<A[i];
    	}
    	cout<<'}'<<endl;
    }

# 三、练习 #

## 6.1 堆 ##

**\[plain\]** [ view plain][view plain] [copy][view plain] [print][view plain] [?][view plain]

1.  6.1-1  
2.  最多2^(h+1) - 1， 最少2 ^ h（当树中只有一个结点时，高度是0）  
3.  6.1-2  
4.  根据上一题，2^h <= n <= 2^(h+1) - 1  
5.   ==> h <= lgn <= h + 1  
6.   ==> lgn = h  
7.  6.1-4  
8.  叶子上  
9.  6.1-5  
10. 是最小堆或最大堆  
11. 6.1-6  
12. 不是，7是6的左孩子，但7>6

6.1-1
    最多2^(h+1) - 1， 最少2 ^ h（当树中只有一个结点时，高度是0）
    6.1-2
    根据上一题，2^h <= n <= 2^(h+1) - 1
     ==> h <= lgn <= h + 1
     ==> lgn = h
    6.1-4
    叶子上
    6.1-5
    是最小堆或最大堆
    6.1-6
    不是，7是6的左孩子，但7>6

## 6.2 保持堆的性质    ##

**\[plain\]** [ view plain][view plain] [copy][view plain] [print][view plain] [?][view plain]

1.  6.2-1  
2.      A = \{27,17,3,16,13,10,1,5,7,12,4,8,9,0\}  
3.  ==> A = \{27,17,10,16,13,3,1,5,7,12,4,8,9,0\}  
4.  ==> A = \{27,17,10,16,13,9,1,5,7,12,4,8,3,0\}  
5.  6.2-2  
6.  MIN-HEAPIFY(A, i)  
7.   1    l <- LEFT(i)  
8.   2    r <- RIGHT(i)  
9.   3    if l <= heap-size\[A\] and A\[l\] < A\[i\]  
10.  4        then smallest <- l  
11.  5        else smallest <- i  
12.  6    if r <= heap-size\[A\] and A\[r\] < \[smallest\]  
13.  7        then smallest <- r  
14.  8    if smallest != i  
15.  9        then exchange A\[i\] <-> A\[smallest\]  
16. 10                MIN\_HEAPIFY(A, smallest)  
17. 6.2-3  
18. 没有效果，程序终止  
19. 6.2-4  
20. i > heap-size\[A\]/2时，是叶子结点，也没有效果，程序终止  
21. 6.2-5 我还是比较喜欢用C++，不喜欢用伪代码  
22. void Heap::Max\_Heapify(int i)  
23. \{  
24.     int l = (LEFT(i)), r = (RIGHT(i)), largest;  
25.     //选择i、i的左、i的右三个结点中值最大的结点  
26.     if(l <= heap\_size && A\[l\] > A\[i\])  
27.         largest = l;  
28.     else largest = i;  
29.     if(r <= heap\_size && A\[r\] > A\[largest\])  
30.         largest = r;  
31.     //如果根最大，已经满足堆的条件，函数停止  
32.     //否则  
33.     while(largest != i)  
34.     \{  
35.         //根与值最大的结点交互  
36.         swap(A\[i\], A\[largest\]);  
37.         //交换可能破坏子树的堆，重新调整子树  
38.         i = largest;  
39.         l = (LEFT(i)), r = (RIGHT(i));  
40.         //选择i、i的左、i的右三个结点中值最大的结点  
41.         if(l <= heap\_size && A\[l\] > A\[i\])  
42.             largest = l;  
43.         else largest = i;  
44.         if(r <= heap\_size && A\[r\] > A\[largest\])  
45.             largest = r;  
46.     \}  
47. \}

6.2-1
        A = {27,17,3,16,13,10,1,5,7,12,4,8,9,0}
    ==> A = {27,17,10,16,13,3,1,5,7,12,4,8,9,0}
    ==> A = {27,17,10,16,13,9,1,5,7,12,4,8,3,0}
    6.2-2
    MIN-HEAPIFY(A, i)
     1    l <- LEFT(i)
     2    r <- RIGHT(i)
     3    if l <= heap-size[A] and A[l] < A[i]
     4        then smallest <- l
     5        else smallest <- i
     6    if r <= heap-size[A] and A[r] < [smallest]
     7        then smallest <- r
     8    if smallest != i
     9        then exchange A[i] <-> A[smallest]
    10                MIN_HEAPIFY(A, smallest)
    6.2-3
    没有效果，程序终止
    6.2-4
    i > heap-size[A]/2时，是叶子结点，也没有效果，程序终止
    6.2-5 我还是比较喜欢用C++，不喜欢用伪代码
    void Heap::Max_Heapify(int i)
    {
    	int l = (LEFT(i)), r = (RIGHT(i)), largest;
    	//选择i、i的左、i的右三个结点中值最大的结点
    	if(l <= heap_size && A[l] > A[i])
    		largest = l;
    	else largest = i;
    	if(r <= heap_size && A[r] > A[largest])
    		largest = r;
    	//如果根最大，已经满足堆的条件，函数停止
    	//否则
    	while(largest != i)
    	{
    		//根与值最大的结点交互
    		swap(A[i], A[largest]);
    		//交换可能破坏子树的堆，重新调整子树
    		i = largest;
    		l = (LEFT(i)), r = (RIGHT(i));
    		//选择i、i的左、i的右三个结点中值最大的结点
    		if(l <= heap_size && A[l] > A[i])
    			largest = l;
    		else largest = i;
    		if(r <= heap_size && A[r] > A[largest])
    			largest = r;
    	}
    }

## 6.3 建堆    ##

**\[plain\]** [ view plain][view plain] [copy][view plain] [print][view plain] [?][view plain]

1.  6.3-1  
2.      A = \{5,3,17,10,84,19,6,22,9\}  
3.  ==> A = \{5,3,17,22,84,19,6,10,9\}  
4.  ==> A = \{5,3,19,22,84,17,6,10,9\}  
5.  ==> A = \{5,84,19,22,3,17,6,10,9\}  
6.  ==> A = \{84,5,19,22,3,17,6,10,9\}  
7.  ==> A = \{84,22,19,5,3,17,6,10,9\}  
8.  ==> A = \{84,22,19,10,3,17,6,5,9\}  
9.  6.3-2  
10. 因为MAX-HEAPIFY中使用条件是当前结点的左孩子和右孩子都是堆

6.3-1
        A = {5,3,17,10,84,19,6,22,9}
    ==> A = {5,3,17,22,84,19,6,10,9}
    ==> A = {5,3,19,22,84,17,6,10,9}
    ==> A = {5,84,19,22,3,17,6,10,9}
    ==> A = {84,5,19,22,3,17,6,10,9}
    ==> A = {84,22,19,5,3,17,6,10,9}
    ==> A = {84,22,19,10,3,17,6,5,9}
    6.3-2
    因为MAX-HEAPIFY中使用条件是当前结点的左孩子和右孩子都是堆

## 6.4 堆排序的算法    ##

**\[plain\]** [ view plain][view plain] [copy][view plain] [print][view plain] [?][view plain]

1.  6.4-1  
2.      A = \{5,13,2,25,7,17,20,8,4\}  
3.  ==> A = \{25,13,20,8,7,17,2,5,4\}  
4.  ==> A = \{4,13,20,8,7,17,2,5,25\}  
5.  ==> A = \{20,13,17,8,7,4,2,5,25\}  
6.  ==> A = \{5,13,17,8,7,4,2,20,25\}  
7.  ==> A = \{17,13,5,8,7,4,2,20,25\}  
8.  ==> A = \{2,13,5,8,7,4,17,20,25\}  
9.  ==> A = \{13,8,5,2,7,4,17,20,25\}  
10. ==> A = \{4,8,5,2,7,13,17,20,25\}  
11. ==> A = \{8,7,5,2,4,13,17,20,25\}  
12. ==> A = \{4,7,5,2,8,13,17,20,25\}  
13. ==> A = \{7,4,5,2,8,13,17,20,25\}  
14. ==> A = \{2,4,5,7,8,13,17,20,25\}  
15. ==> A = \{5,4,2,7,8,13,17,20,25\}  
16. ==> A = \{2,4,5,7,8,13,17,20,25\}  
17. ==> A = \{4,2,5,7,8,13,17,20,25\}  
18. ==> A = \{2,4,5,7,8,13,17,20,25\}  
19. ==> A = \{2,4,5,7,8,13,17,20,25\}  
20. 6.4-3  
21. 按递增排序的数组，运行时间是nlgn  
22. 按递减排序的数组，运行时间是n

6.4-1
        A = {5,13,2,25,7,17,20,8,4}
    ==> A = {25,13,20,8,7,17,2,5,4}
    ==> A = {4,13,20,8,7,17,2,5,25}
    ==> A = {20,13,17,8,7,4,2,5,25}
    ==> A = {5,13,17,8,7,4,2,20,25}
    ==> A = {17,13,5,8,7,4,2,20,25}
    ==> A = {2,13,5,8,7,4,17,20,25}
    ==> A = {13,8,5,2,7,4,17,20,25}
    ==> A = {4,8,5,2,7,13,17,20,25}
    ==> A = {8,7,5,2,4,13,17,20,25}
    ==> A = {4,7,5,2,8,13,17,20,25}
    ==> A = {7,4,5,2,8,13,17,20,25}
    ==> A = {2,4,5,7,8,13,17,20,25}
    ==> A = {5,4,2,7,8,13,17,20,25}
    ==> A = {2,4,5,7,8,13,17,20,25}
    ==> A = {4,2,5,7,8,13,17,20,25}
    ==> A = {2,4,5,7,8,13,17,20,25}
    ==> A = {2,4,5,7,8,13,17,20,25}
    6.4-3
    按递增排序的数组，运行时间是nlgn
    按递减排序的数组，运行时间是n

## 6.5 优先级队列    ##

**\[plain\]** [ view plain][view plain] [copy][view plain] [print][view plain] [?][view plain]

1.  6.5-1  
2.      A = \{15,13,9,5,12,8,7,4,0,6,2,1\}  
3.  ==> A = \{1,13,9,5,12,8,7,4,0,6,2,1\}  
4.  ==> A = \{13,1,9,5,12,8,7,4,0,6,2,1\}  
5.  ==> A = \{13,12,9,5,1,8,7,4,0,6,2,1\}  
6.  ==> A = \{13,12,9,5,6,8,7,4,0,1,2,1\}  
7.  return 15  
8.  6.5-2  
9.      A = \{15,13,9,5,12,8,7,4,0,6,2,1\}  
10. ==> A = \{15,13,9,5,12,8,7,4,0,6,2,1,-2147483647\}  
11. ==> A = \{15,13,9,5,12,8,7,4,0,6,2,1,10\}  
12. ==> A = \{15,13,9,5,12,10,7,4,0,6,2,1,8\}  
13. ==> A = \{15,13,10,5,12,9,7,4,0,6,2,1,8\}  
14. 6.5-3  
15. HEAP-MINIMUM(A)  
16. 1    return A\[1\]  
17. HEAP-EXTRACR-MIN(A)  
18. 1    if heap-size\[A\] < 1  
19. 2        then error "heap underflow"  
20. 3    min <- A\[1\]  
21. 4    A\[1\] <- A\[heap-size\[A\]\]  
22. 5    heap-size\[A\] <- heap-size\[A\] - 1  
23. 6    MIN-HEAPIFY(A, 1)  
24. 7    return min  
25. HEAP-DECREASE-KEY(A, i, key)  
26. 1    if key > A\[i\]  
27. 2        then error "new key is smaller than current key"  
28. 3    A\[i\] <- key  
29. 4    while i > 1 and A\[PARENT(i)\] > A\[i\]  
30. 5        do exchange A\[i\] <-> A\[PARENT(i)\]  
31. 6              i <- PARENT(i)  
32. MIN-HEAP-INSERT  
33. 1    heap-size\[A\] <- heap-size\[A\] + 1  
34. 2    A\[heap-size\[A\]\] <- 0x7fffffff  
35. 3    HEAP-INCREASE-KEY(A, heap-size\[A\], key)  
36. 6.5-4  
37. 要想插入成功，key必须大于这个初值。key可能是任意数，因此初值必须是无限小  
38. 6.5-6  
39. FIFO：以进入队列的时间作为权值建立最小堆  
40. 栈：以进入栈的时间作为权值建立最大堆  
41. 6.5-7  
42. void Heap::Heap\_Delete(int i)  
43. \{  
44.     if(i > heap\_size)  
45.     \{  
46.         cout<<"there's no node i"<<endl;  
47.         exit(0);  
48.     \}  
49.     int key = A\[heap\_size\];  
50.     heap\_size--;  
51.     if(key > A\[i\])   //最后一个结点不一定比中间的结点最  
52.         Heap\_Increase\_Key(i, key);  
53.     else  
54.     \{  
55.         A\[i\] = key;  
56.         Max\_Heapify(i);  
57.     \}  
58. \}

6.5-1
        A = {15,13,9,5,12,8,7,4,0,6,2,1}
    ==> A = {1,13,9,5,12,8,7,4,0,6,2,1}
    ==> A = {13,1,9,5,12,8,7,4,0,6,2,1}
    ==> A = {13,12,9,5,1,8,7,4,0,6,2,1}
    ==> A = {13,12,9,5,6,8,7,4,0,1,2,1}
    return 15
    6.5-2
        A = {15,13,9,5,12,8,7,4,0,6,2,1}
    ==> A = {15,13,9,5,12,8,7,4,0,6,2,1,-2147483647}
    ==> A = {15,13,9,5,12,8,7,4,0,6,2,1,10}
    ==> A = {15,13,9,5,12,10,7,4,0,6,2,1,8}
    ==> A = {15,13,10,5,12,9,7,4,0,6,2,1,8}
    6.5-3
    HEAP-MINIMUM(A)
    1    return A[1]
    HEAP-EXTRACR-MIN(A)
    1    if heap-size[A] < 1
    2        then error "heap underflow"
    3    min <- A[1]
    4    A[1] <- A[heap-size[A]]
    5    heap-size[A] <- heap-size[A] - 1
    6    MIN-HEAPIFY(A, 1)
    7    return min
    HEAP-DECREASE-KEY(A, i, key)
    1    if key > A[i]
    2        then error "new key is smaller than current key"
    3    A[i] <- key
    4    while i > 1 and A[PARENT(i)] > A[i]
    5        do exchange A[i] <-> A[PARENT(i)]
    6              i <- PARENT(i)
    MIN-HEAP-INSERT
    1    heap-size[A] <- heap-size[A] + 1
    2    A[heap-size[A]] <- 0x7fffffff
    3    HEAP-INCREASE-KEY(A, heap-size[A], key)
    6.5-4
    要想插入成功，key必须大于这个初值。key可能是任意数，因此初值必须是无限小
    6.5-6
    FIFO：以进入队列的时间作为权值建立最小堆
    栈：以进入栈的时间作为权值建立最大堆
    6.5-7
    void Heap::Heap_Delete(int i)
    {
    	if(i > heap_size)
    	{
    		cout<<"there's no node i"<<endl;
    		exit(0);
    	}
    	int key = A[heap_size];
    	heap_size--;
    	if(key > A[i])   //最后一个结点不一定比中间的结点最
    		Heap_Increase_Key(i, key);
    	else
    	{
    		A[i] = key;
    		Max_Heapify(i);
    	}
    }

6.5-8

见 [算法导论6.5-8堆排序-K路合并][6.5-8_-K]

# 四、思考题    #

## 6-1 用插入方法建堆    ##

**\[cpp\]** [ view plain][view plain] [copy][view plain] [print][view plain] [?][view plain]

1.  void Heap::Build\_Max\_Heap()  
2.  \{  
3.      heap\_size = 1;  
4.      //从堆中最后一个元素开始，依次调整每个结点，使符合堆的性质    
5.      for(int i = 2; i <= length; i++)  
6.          Max\_Heap\_Insert(A\[i\]);  
7.  \}  
8.  答：  
9.  a）A = \{1,2,3\};

void Heap::Build_Max_Heap()
    {
    	heap_size = 1;
    	//从堆中最后一个元素开始，依次调整每个结点，使符合堆的性质
    	for(int i = 2; i <= length; i++)
    		Max_Heap_Insert(A[i]);
    }
    答：
    a）A = {1,2,3};

## 6-2 对d叉堆的分析 ##

**\[plain\]** [ view plain][view plain] [copy][view plain] [print][view plain] [?][view plain]

1.  a）根结点是A\[1\]，根结点的孩子是A\[2\],A\[3\],……，A\[d+1\]  
2.  PARENT(i) = (i - 2 ) / d + 1    
3.  CHILD(i, j ) = d \* (i - 1) + j + 1    
4.  b）lgn/lgd    
5.  c）HEAP-EXTRACR-MAX(A)与二叉堆的实现相同，其调用的MAX-HEAPIFY(A, i)要做部分更改，时间复杂度是O(lgn/lgd \* d)    
6.  MAX-HEAPIFY(A, i)  
7.  1    largest <- A\[i\]    
8.  2    for j <- 1 to d  
9.  3        k <- CHILD(i, j)    
10. 4        if k <= heap-size\[A\] and A\[j\] > A\[largest\]    
11. 5            largest <- k  
12. 6    if largest != i    
13. 7    then exchange A\[i\] <-> A\[largest\]    
14. 8             MAX-HEAPIFY(A, largest)    
15. d）和二叉堆的实现完全一样，时间复杂度是O(lgn/lgd)    
16. e）和二叉堆的实现完全一样，时间复杂度是O(lgn/lgd)

a）根结点是A[1]，根结点的孩子是A[2],A[3],……，A[d+1]
    PARENT(i) = (i - 2 ) / d + 1  
    CHILD(i, j ) = d * (i - 1) + j + 1  
    b）lgn/lgd  
    c）HEAP-EXTRACR-MAX(A)与二叉堆的实现相同，其调用的MAX-HEAPIFY(A, i)要做部分更改，时间复杂度是O(lgn/lgd * d)  
    MAX-HEAPIFY(A, i)
    1    largest <- A[i]  
    2    for j <- 1 to d
    3        k <- CHILD(i, j)  
    4        if k <= heap-size[A] and A[j] > A[largest]  
    5            largest <- k
    6    if largest != i  
    7    then exchange A[i] <-> A[largest]  
    8             MAX-HEAPIFY(A, largest)  
    d）和二叉堆的实现完全一样，时间复杂度是O(lgn/lgd)  
    e）和二叉堆的实现完全一样，时间复杂度是O(lgn/lgd)

## 6-3 Young氏矩阵 ##

见 [算法导论 6-3 Young氏矩阵][6-3 Young]

转载自： [http://blog.csdn.net/mishifangxiangdefeng/article/details/7662515][http_blog.csdn.net_mishifangxiangdefeng_article_details_7662515]

[view plain]: http://blog.csdn.net/mishifangxiangdefeng/article/details/7662515#
[6.5-8_-K]: http://blog.csdn.net/mishifangxiangdefeng/article/details/7668486
[6-3 Young]: http://blog.csdn.net/mishifangxiangdefeng/article/details/7976452
[http_blog.csdn.net_mishifangxiangdefeng_article_details_7662515]: http://blog.csdn.net/mishifangxiangdefeng/article/details/7662515