鱼C论坛

 找回密码
 立即注册

算法导论第六章堆排序所给的伪代码转换具体程序

已有 264 次阅读2014-1-4 09:29 |个人分类:数据结构与算法

首先show下我自己写的不带类的C++代码
  1. #include <iostream>  
  2. using namespace std;  
  3. const length=100;  
  4. int A[length]={1,9,10,2,7,5,6,4,13,3,18,11,100};  
  5. int Heap_size(int A[]);//始终是数组内从后往前数的第一个非0数开始的一组数。  
  6. int heap_size=Heap_size(A);  
  7. int PARENT(int i);//父节点  
  8. int LEFT(int i);//左孩子结点  
  9. int RIGHT(int i);//有孩子结点  
  10. void MAX_HEAPIFY(int A[],int i);//保持最大堆  
  11. void BUILD_MAX_HEAP(int A[]);//建立最大堆  
  12. void Print(int A[]);  
  13. void Print1(int A[]);  
  14. void HEAPSORT(int A[]);//最大堆排序  
  15. int MAXIMUM(int A[]);  
  16. int HEAP_EXTRACT_MAX(int A[]);//删除最大堆中的最大元素。  
  17. void HEAP_INCREASE_KEY(int A[],int i,int key);//第i个位置的值增加为key  
  18. void MAX_HEAP_INSERT(int A[],int key);  
  19. void main()  
  20. {  
  21.     int A[length]={1,9,10,2,7,5,6,4,13,3,18,11,100};  
  22.     cout<<"数组初始化:"<<endl;  
  23.     Print(A);  
  24.     cout<<"建立最大堆:"<<endl;  
  25.     BUILD_MAX_HEAP(A);  
  26.     Print(A);  
  27.     cout<<"删除最大堆的当前最大元素:"<<endl;  
  28.     HEAP_EXTRACT_MAX(A);  
  29.     Print(A);  
  30.     cout<<"最大堆第8位的数增加到15:"<<endl;  
  31.     HEAP_INCREASE_KEY(A,8,15);  
  32.     Print(A);  
  33.     cout<<"最大堆插入一个元素56:"<<endl;  
  34.     MAX_HEAP_INSERT(A,56);  
  35.     Print(A);  
  36.     cout<<"最大堆排序后的数组为:"<<endl;  
  37.     HEAPSORT(A);  
  38.     Print1(A);  
  39. }  
  40. int PARENT(int i)  
  41. {  
  42.     return (i-1)/2;  
  43. }  
  44. int LEFT(int i)  
  45. {  
  46.     return 2*i+1;  
  47. }  
  48. int RIGHT(int i)  
  49. {  
  50.     return 2*i+2;  
  51. }  
  52. void MAX_HEAPIFY(int A[],int i)  
  53. {  
  54.     int largest=0;  
  55.     int L=LEFT(i);  
  56.     int R=RIGHT(i);  
  57.     if (L<heap_size&&A[L]>A[i])  
  58.     {  
  59.         largest=L;  
  60.     }  
  61.     else largest=i;  
  62.     if (R<heap_size&&A[R]>A[largest])  
  63.     {  
  64.         largest=R;  
  65.     }  
  66.     if (largest!=i)  
  67.     {  
  68.         swap(A[i],A[largest]);  
  69.         MAX_HEAPIFY(A,largest);  
  70.     }  
  71. }  
  72. void BUILD_MAX_HEAP(int A[])  
  73. {  
  74.     int heap_size=length;  
  75.     for (int i=length/2;i>=0;i--)  
  76.     {  
  77.         MAX_HEAPIFY(A,i);  
  78.     }  
  79. }  
  80. void HEAPSORT(int A[])  
  81. {  
  82.     BUILD_MAX_HEAP(A);  
  83.     for (int i=Heap_size(A)-1;i>=0;i--)  
  84.     {  
  85.         swap(A[0],A[i]);  
  86.         heap_size--;  
  87.         MAX_HEAPIFY(A,0);  
  88.     }  
  89. }  
  90. int MAXIMUM(int A[])  
  91. {  
  92.     return A[0];  
  93. }  
  94. int HEAP_EXTRACT_MAX(int A[])  
  95. {  
  96.     if (heap_size<0)  
  97.     {  
  98.         cout<<"heap underflow"<<endl;    
  99.         exit(0);   
  100.     }  
  101.     int max=A[0];  
  102.     A[0]=A[heap_size-1];  
  103.     heap_size--;  
  104.     MAX_HEAPIFY(A,0);  
  105.     A[heap_size]=0;  
  106.     return max;  
  107. }  
  108. void HEAP_INCREASE_KEY(int A[],int i,int key)  
  109. {  
  110.     if (key<A[i])  
  111.     {  
  112.         return ;  
  113.     }  
  114.     A[i]=key;  
  115.     while (i>0&&A[PARENT(i)]<A[i])  
  116.     {  
  117.         swap(A[i],A[PARENT(i)]);  
  118.         i=PARENT(i);  
  119.     }  
  120. }  
  121. void MAX_HEAP_INSERT(int A[],int key)  
  122. {  
  123.     heap_size++;  
  124.     A[heap_size-1]=-0x7fffffff;  
  125.     HEAP_INCREASE_KEY(A,heap_size-1,key);  
  126. }  
  127. int Heap_size(int A[])  
  128. {  
  129.     for (int i=length-1;i>=0;i--)  
  130.     {  
  131.         if (A[i]>0)  
  132.         {  
  133.             return i+1;  
  134.         }  
  135.     }  
  136.     return -1;  
  137. }  
  138. void Print(int A[])  
  139. {  
  140.     for (int i=0;i<heap_size;i++)  
  141.     {  
  142.         if(A[i]>0)  
  143.             cout<<A[i]<<" ";  
  144.     }  
  145.     cout<<endl;  
  146. }  
  147. void Print1(int A[])  
  148. {  
  149.     for (int i=0;i<length;i++)  
  150.     {  
  151.         if(A[i]>0)  
  152.             cout<<A[i]<<" ";  
  153.     }  
  154.     cout<<endl;  
  155. }  

下面是CSDN网友给的答案:这个代码完全忽略了边界问题,所以带来了一些错误问题

下面是我基于网友给的代码基础上改的,经过我调整了多个函数的边界/条件后,用类的方法得以完美解决。

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

下面是6.5-3课后题引申的最小堆问题

下面是不带类的C++代码

  1. #include <iostream>  
  2. using namespace std;  
  3. const length=100;  
  4. int A[length]={1,9,10,2,7,5,6,4,13,3,18,11,100};  
  5. int PARENT(int i);//父节点  
  6. int LEFT(int i);//左孩子结点  
  7. int RIGHT(int i);//有孩子结点  
  8. void MIN_HEAPIFY(int A[],int i);//保持最小堆  
  9. void BUILD_MIN_HEAP(int A[]);//建立最小堆  
  10. void Print(int A[]);  
  11. void Print1(int A[]);  
  12. int Heap_size(int A[]);//始终是数组内从后往前数的第一个非0数开始的一组数。void HEAPSORT(int A[]);//最小堆排序  
  13. void HEAPSORT(int A[]);  
  14. int MINIMUM(int A[]);  
  15. int HEAP_EXTRACT_MIN(int A[]);//删除最大堆中的最小元素。  
  16. void HEAP_INCREASE_KEY(int A[],int i,int key);//第i个位置的值增加为key  
  17. void MIN_HEAP_INSERT(int A[],int key);  
  18. int heap_size=Heap_size(A);  
  19. void main()  
  20. {  
  21.     cout<<"数组初始化:"<<endl;  
  22.     Print(A);  
  23.     cout<<"建立最小堆:"<<endl;  
  24.     BUILD_MIN_HEAP(A);  
  25.     Print(A);  
  26.     cout<<"删除最小堆的当前最小元素:"<<endl;  
  27.     HEAP_EXTRACT_MIN(A);  
  28.     Print(A);  
  29.     cout<<"最小堆第8位的数增加到15:"<<endl;  
  30.     HEAP_INCREASE_KEY(A,8,15);  
  31.     Print(A);  
  32.     cout<<"最小堆插入一个元素56:"<<endl;  
  33.     MIN_HEAP_INSERT(A,56);  
  34.     Print(A);  
  35.     cout<<"最小堆排序后的数组为:"<<endl;  
  36.     HEAPSORT(A);  
  37.     Print1(A);  
  38. }  
  39. int PARENT(int i)  
  40. {  
  41.     return (i-1)/2;  
  42. }  
  43. int LEFT(int i)  
  44. {  
  45.     return 2*i+1;  
  46. }  
  47. int RIGHT(int i)  
  48. {  
  49.     return 2*i+2;  
  50. }  
  51. void MIN_HEAPIFY(int A[],int i)  
  52. {  
  53.     int largest=0;  
  54.     int L=LEFT(i);  
  55.     int R=RIGHT(i);  
  56.     if (L<heap_size&&A[L]<A[i])  
  57.     {  
  58.         largest=L;  
  59.     }  
  60.     else largest=i;  
  61.     if (R<heap_size&&A[R]<A[largest])  
  62.     {  
  63.         largest=R;  
  64.     }  
  65.     if (largest!=i)  
  66.     {  
  67.         swap(A[i],A[largest]);  
  68.         MIN_HEAPIFY(A,largest);  
  69.     }  
  70. }  
  71. void BUILD_MIN_HEAP(int A[])  
  72. {  
  73.     int heap_size=length;  
  74.     for (int i=length/2;i>=0;i--)  
  75.     {  
  76.         MIN_HEAPIFY(A,i);  
  77.     }  
  78. }  
  79. void HEAPSORT(int A[])  
  80. {  
  81.     BUILD_MIN_HEAP(A);  
  82.     for (int i=Heap_size(A)-1;i>=1;i--)  
  83.     {  
  84.         swap(A[0],A[i]);  
  85.         heap_size--;  
  86.         MIN_HEAPIFY(A,0);  
  87.     }  
  88. }  
  89. int MINIMUM(int A[])  
  90. {  
  91.     return A[0];  
  92. }  
  93. int HEAP_EXTRACT_MIN(int A[])  
  94. {  
  95.     if (heap_size<0)  
  96.     {  
  97.         cout<<"heap underflow"<<endl;    
  98.         exit(0);   
  99.     }  
  100.     int min=A[0];  
  101.     A[0]=A[heap_size-1];  
  102.     heap_size--;  
  103.     MIN_HEAPIFY(A,0);  
  104.     A[heap_size]=0;  
  105.     return min;  
  106. }  
  107. void HEAP_INCREASE_KEY(int A[],int i,int key)  
  108. {  
  109.     if (key<A[i])  
  110.     {  
  111.         return ;  
  112.     }  
  113.     A[i]=key;  
  114.     while (i>0&&A[PARENT(i)]>A[i])  
  115.     {  
  116.         swap(A[i],A[PARENT(i)]);  
  117.         i=PARENT(i);  
  118.     }  
  119. }  
  120. void MIN_HEAP_INSERT(int A[],int key)  
  121. {  
  122.     heap_size++;  
  123.     A[heap_size-1]=-0x7fffffff;  
  124.     HEAP_INCREASE_KEY(A,heap_size-1,key);  
  125. }  
  126. int Heap_size(int A[])  
  127. {  
  128.     for (int i=length-1;i>=0;i--)  
  129.     {  
  130.         if (A[i]>0)  
  131.         {  
  132.             return i+1;  
  133.         }  
  134.     }  
  135.     return -1;  
  136. }  
  137. void Print(int A[])  
  138. {  
  139.     for (int i=0;i<heap_size;i++)  
  140.     {  
  141.         if(A[i]>0)  
  142.          cout<<A[i]<<" ";  
  143.     }  
  144.     cout<<endl;  
  145. }  
  146. void Print1(int A[])  
  147. {  
  148.     for (int i=0;i<length;i++)  
  149.     {  
  150.         if(A[i]>0)  
  151.             cout<<A[i]<<" ";  
  152.     }  
  153.     cout<<endl;  
  154. }  

下面是带类的C++最小堆代码:

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


路过

雷人

握手

鲜花

鸡蛋

评论 (0 个评论)

facelist

您需要登录后才可以评论 登录 | 立即注册

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-7-17 02:29

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

返回顶部