算法导论第六章6.5有限队列中的6.5-9课后练习

由题目提示知，需要用到归并排序，又要用到最小堆，那么我想到用含有最小堆排序的归并排序对k个有序数组进行合并因为链表可以看成特殊的动态数组，那么我把链表替换成数组求解。先把k个数组放入到一个新数组A中，那么一共就有k=n/a个数组(a为k个元素数组中所含最多元素的数量)

[cpp] view plaincopy

1. <span style="font-size:18px;">#include <iostream>  
2. using namespace std;  
3. const length=100;  
4. int LEFT(int i);  
5. int RIGHT(int i);  
6. void MIN_HEAPIFY(int A[],int i);  
7. void BUILD_MIN_HEAP(int A[],int p,int q);  
8. int*  HEAPSORT(int A[],int B[],int p,int q,int r);  
9. void MERGE(int A[],int p,int q,int r);  
10. void MERGE_SORT(int A[],int p,int r,int k);  
11. int heap_size=length,a=4;  
12. void main()  
13. {  
14.     int B[8][4]={{8,16,19},{1,9},{2,10,17,20},{3,11},{4,12},{5,13},{6,14,18},{7,15}};//这是k=8个数组在一个2维数组中  
15.     int A[length]={0};  
16.     for(int i=0,h=0;i<8;i++)//将k=8个数组合并到一个新数组中。  
17.     {  
18.         for (int j=0;j<4;j++,h++)  
19.         {  
20.             if(B[i][j]!=0) A[h]=B[i][j];  
21.         }  
22.     }//这个双重循环含k*a=n个元素 运行时间为O(n)  
23.     MERGE_SORT(A,0,length-1,a);//然后将新数组每a=4个有序数进行归并,注意a值的选择 2<=a<=√总元素n <strong><em><u>（注释1）</u></em></strong>  
24.     cout<<"排序后："<<endl;  
25.     for (  i=0;i<length;i++)  
26.     {  
27.          if(A[i]>0)  
28.          cout<<A[i]<<" ";  
29.     }  
30.     cout<<endl;    
31. }  
32. int LEFT(int i)  
33. {  
34.     return 2*i+1;  
35. }  
36. int RIGHT(int i)  
37. {  
38.     return 2*i+2;  
39. }  
40. void MIN_HEAPIFY(int A[],int i)  
41. {  
42.     int largest=0;  
43.     int L=LEFT(i);  
44.     int R=RIGHT(i);  
45.     if (L<heap_size&&A[L]<A[i])  
46.     {  
47.         largest=L;  
48.     }  
49.     else largest=i;  
50.     if (R<heap_size&&A[R]<A[largest])  
51.     {  
52.         largest=R;  
53.     }  
54.     if (largest!=i)  
55.     {  
56.         swap(A[i],A[largest]);  
57.         MIN_HEAPIFY(A,largest);  
58.     }  
59. }  
60. void BUILD_MIN_HEAP(int A[],int p,int q)  
61. {  
62.     heap_size=q;  
63.     for (int i=q/2;i>=p;i--)  
64.     {  
65.         MIN_HEAPIFY(A,i);  
66.     }  
67. }  
68. int* HEAPSORT(int A[],int B[],int p,int q,int r)  
69. {  
70.     for (int i=p,j=0;i<=q,j<r;i++,j++)  
71.     {  
72.         B[j]=A[i];  
73.     }  
74.     BUILD_MIN_HEAP(B,0,r);  
75.     for ( i=r-1;i>=1;i--)  
76.     {  
77.         swap(B[0],B[i]);  
78.         heap_size--;  
79.         MIN_HEAPIFY(B,0);  
80.     }  
81.     return B;  
82. }  
83. void MERGE(int A[],int p,int q,int r)  
84. {  
85.     int n1=q-p+1,n2=r-q,i,j,flag=-1;  
86.     int *L=new int[n1];  
87.     int *R=new int[n2];  
88.     L=HEAPSORT(A,L,p,q,n1);//归并时，用最小堆排序   
89.     R=HEAPSORT(A,R,q+1,r,n2);  
90.     i=0;j=0;  
91.     L[n1]=flag;  
92.     R[n2]=flag;  
93.     for (int k=p;k<=r;k++)  
94.     {  
95.         if (L[i]==flag)  
96.         {  
97.             A[k]=R[j];  
98.             j++;  
99.         }  
100.         else if (R[j]==flag)  
101.         {  
102.             A[k]=L[i];  
103.             i++;  
104.         }  
105.         else if (L[i]>=R[j])  
106.         {  
107.             A[k]=L[i];  
108.             i++;  
109.         }  
110.         else   
111.         {  
112.             A[k]=R[j];  
113.             j++;  
114.         }  
115.     }  
116. }  
117. void MERGE_SORT(int A[],int p,int r,int k)  
118. {  
119.     int q=(r+p)/k;  
120.     if((q-p+1)<k)      
121.     {               
122.        return;  
123.     }   
124.     else  
125.     {  
126.         MERGE_SORT(A,p,q,k);   
127.         MERGE_SORT(A,q+1,r,k);  
128.         MERGE(A,p,q,r);  
129.     }  
130. }  
131.