算法导论第六章堆排序思考题

         最终生成的最大堆为： A={16,14,10,8,2,3,9,1,4}

6.2(对d叉堆的分析)d叉堆与二叉堆很类似，但(一个可能的例外是)其中的每个非叶结点有d个孩子，而不是仅仅2个。


a.如何在一个数组中表示一个d叉堆？
b.包含n个元素的d叉堆的高度是多少？ 请用n和d表示。
c.请给出EXTRACT-MAX在d叉最大堆上的一个有效实现，并用d和n表示出它的时间复杂度。
d.给出INSERT在d叉最大堆上的一个有效实现。并用d和n表示出它的时间复杂度。
e.给出INCREASE-KEY(A,i,k)的一个有效实现。当k<A[i]时，它会触发一个错误，否则执行A[i]=k,并更新相应的d叉最大堆。并用d和n表示出它的
时间复杂度。


a.我们可以把d叉堆近似看成完全d叉树，除了最底层外，该树是完全充满的，给定一个下标i.有
i的父结点为：PARENT(i) return (i+2)/d  i的最左孩子结点为：LEFT(i) return (i-1)d+2


b.设一个有着n个元素的d叉堆的高度h 则d^0+d^1+...+d^h=n => h=log(d,n)


c.给出EXTRACT-MAX函数实现实际上是需要给出MAX-HEAPIFY(A,1)具体实现，因为在实现d叉堆删除最大元素时，EXTRACT-MAX函数中除了
MAX-HEAPIFY(A,1)函数实现和二叉堆不一样外，其他原理都是一样的。下面给出MAX-HEAPIFY(A,1)具体实现。

[cpp] view plaincopy

1. <span style="font-size:18px;">MAX-HEAPIFY(A,i)  
2. L=LEFT(i)  
3. for i=1 to d  
4.   if(A[L+i]>max)  
5.    max=A[L+i]  
6.    r=L+i  
7. if(r<=A.heap-size and A[r]>A[i] )  
8.    largest=r//由于这个largest已经是最大值，所以省略了原书伪代码6-7行中的内容  
9. else largest=i  
10. if largest!=i  
11.    exchange A[i] with A[largest]  
12.    MAX-HEAPIFY(A,largest)  

6.3(Young氏矩阵) 在一个mXn的Young氏矩阵中，每一行的数据都是从左到右排序的，每一列的数据都是从上到下排序的。Young氏矩阵也会存
在一些值为无穷大的数据项，表示哪些不存在的元素。因此，Young氏矩阵可以用来存储r<=mn个有限的数。

(a)很容易 这里就不给出了。

(b)因为Young氏矩阵从左到右，从上到下，都是递增数列(以下程序也是基于这个原因来运行的)，所以如果第一个元素为无穷大，那么以第一个元素

为中心，向右或者向下的元素都是无穷大，不可能比第一个元素小，因为这样就不满足递增的性质了，所以整个矩阵都是无穷大不存在的数，矩阵

应该为空。如果最后一个元素小于无穷大也就是有有效值，那么以这个元素为中心，还是递增数列的性质决定了，向上或向左的元素都应该比这个元

素小。所以整个矩阵都含有有效值，矩阵肯定是满的。

[cpp] view plaincopy

1. <span style="font-size:18px;">#include <iostream>  
2. using namespace std;  
3. const m=4;const n=5;  
4. void Print(int A[][5]);  
5. int Young_EXTRACT_MIN(int A[][5],int i,int j)//young氏矩阵的删除  
6. {//删除最小值，我们用递归函数把删除的数通过两个方向的比较移动到矩阵右下角  
7.     static int k=0;  
8.     static int h=0;  
9.     int min=A[0][0];  
10.     if (k==h)  
11.     {  
12.         A[0][0]=A[m-1][n-1]+1;  
13.     }  
14.     k++;  
15.     if (i==m-1&&j==n-1)  
16.     {  
17.         return -1;  
18.     }  
19.     else   
20.     {  
21.         if (A[i][j+1]<=A[i+1][j]&&j!=n-1)  
22.         {  
23.             swap(A[i][j+1],A[i][j]);  
24.             Young_EXTRACT_MIN(A,i,j+1);  
25.         }  
26.         else if (A[i][j+1]>=A[i+1][j]&&i!=m-1)  
27.         {  
28.             swap(A[i+1][j],A[i][j]);  
29.             Young_EXTRACT_MIN(A,i+1,j);  
30.         }  
31.         else if (A[i][j]>=A[i+1][j]&&j==n-1)  
32.         {  
33.             swap(A[i][j],A[i+1][j]);  
34.             Young_EXTRACT_MIN(A,i+1,j);  
35.         }  
36.         else if (A[i][j]>=A[i][j+1]&&i==m-1)  
37.         {  
38.             swap(A[i][j],A[i][j+1]);  
39.             Young_EXTRACT_MIN(A,i,j+1);  
40.         }  
41.     }  
42.     h=k;  
43.     return min;  
44. }  
45. void Young_INSERT(int A[][5],int i,int j,int key)  
46. {//插入与删除类似。  
47.    static int k=0;  
48.    if (k==0)  
49.    {  
50.       i=m-1;j=n-1;  
51.       A[i][j]=key;//因为这个young氏矩阵元素不满，所以矩阵最后一个位置必是不存在值  
52.    }  
53.    k=1;  
54.    if (i==0&&j==0)  
55.    {  
56.        return ;  
57.    }  
58.    else if(A[i-1][j]<=A[i][j]&&A[i][j-1]<=A[i][j])  
59.    {  
60.        return ;  
61.    }  
62.    else   
63.    {  
64.        if (A[i][j-1]>=A[i-1][j]&&j!=0)  
65.        {  
66.            swap(A[i][j-1],A[i][j]);  
67.            Young_INSERT(A,i,j-1,key);  
68.        }  
69.        else if (A[i][j-1]<=A[i-1][j]&&i!=0)  
70.        {  
71.            swap(A[i-1][j],A[i][j]);  
72.            Young_INSERT(A,i-1,j,key);  
73.        }  
74.        else if (A[i][j]<=A[i-1][j]&&j==0)  
75.        {  
76.            swap(A[i][j],A[i-1][j]);  
77.            Young_INSERT(A,i-1,j,key);  
78.        }  
79.        else if (A[i][j]<=A[i][j-1]&&i==0)  
80.        {  
81.            swap(A[i][j],A[i][j-1]);  
82.            Young_INSERT(A,i,j-1,key);  
83.        }  
84.     }  
85.      
86. }  
87. void Young_sort(int A[][5])  
88. {//排序我们通过循环调用Young_EXTRACT_MIN函数进行排序  
89.     int kk=m*n,t;  
90.    for (int h=0;h<kk;h++)//O()  
91.    {    
92.        t=Young_EXTRACT_MIN( A,0,0);  
93.        if(t!=10000)  
94.        {  
95.           cout<<t<<" ";//O(m+n)  
96.        }  
97.    }  
98.    cout<<endl;  
99. }  
100. int Young_find(int A[][5],int i,int j,int key)  
101. {//查找我们用递归函数，这里难点是矩阵4个角，左上和右下角因为在横竖方向上均是递增数组，  
102. //所以不可取，至少我还没有发现取这两个角能实现查找功能的方法。另外2个角横竖方向上一增一减有利于查找比较  
103.     static flag=0,t=0;  
104.     if (t==0)  
105.     {  
106.         i = 0, j = n-1;//我们取 Young氏矩阵右上角作为起始位置开始查找。  
107.     }  
108.     t=1;  
109.     if (A[i][j] == key)  
110.     {  
111.         flag++;  
112.         return flag;  
113.     }  
114.     else if(A[i][j] > key&&i!=m&&j!=-1)  
115.     {   
116.        Young_find(A,i,j-1,key);   
117.     }  
118.     else if(A[i][j] < key&&i!=m&&j!=-1)   
119.     {   
120.        Young_find(A,i+1,j,key);  
121.     }  
122.     return flag;  
123. }    
124. void Print(int A[][5])//辅助输出函数  
125. {  
126.     for (int i=0;i<m;i++)//10000以上的数都表示不存在的数。  
127.     {  
128.         for (int j=0;j<n;j++)  
129.         {    
130.             cout<<A[i][j]<<"\t";  
131.         }  
132.         cout<<endl;  
133.     }  
134. }  
135. void main()  
136. {  
137.     int A[m][n]={{1,5,10,20,24},{4,30,35,52,55},{18,43,48,60,10000},{19,45,49,10000,10000}},x;  
138.     cout<<"初始化："<<endl;  
139.     Print(A);  
140.     cout<<endl;  
141.     cout<<"删除当前矩阵最小值"<<endl;  
142.     Young_EXTRACT_MIN(A,0,0);//删除矩阵最小值  
143.     Print(A);  
144.     cout<<"请输入待插入的数"<<endl;  
145.     cin>>x;  
146.     Young_INSERT(A,4,5,x);//插入特定值矩阵  
147.     Print(A);  
148.     cout<<"请输入待查找的数"<<endl;  
149.     cin>>x;  
150.     if(Young_find(A,0,0,x)) cout<<"已经找到"<<endl;  
151.     else cout<<"没有找到"<<endl;  
152.     cout<<"Young氏矩阵排序后："<<endl;  
153.     Young_sort(A);  
154.     //(c)题的时间复杂度：T(p)=T(p-1)+c 每次递归或减少1位i或减少1位j//p=m+n T(p)=cp=O(p)=O(m+n)