Liny_@NotePad

沉迷ACG中

合并堆算法

YOYO posted @ 2009年3月10日 21:31 in 【算法】与【数据结构】 with tags 堆 , 4909 阅读

编写一个算法，把两个相同大小的堆合并成一个堆。

  1. /*
  2. * Title: 编写一个算法，把两个相同大小的堆，合并成一个堆。
  3. * Author: YOYO
  4. * Time: 2009-3-8
  5. *
  6. * 合并算法即其中的merge_heaps(Type A[], Type B[], Type C[], int n)
  7. * 该算法将两个相同大小的堆A和B合并为一个大顶堆，并存储到C中。时间复杂度为O(n*log(n))
  8. *
  9. */
  10. #include<iostream>
  11. using namespace std;
  12.  
  13. #define Type int
  14. #define N 100
  15.  
  16. void shift_up(Type H[], int i);
  17. void shift_down(Type H[], int n, int i);
  18. void insert(Type H[], int &n, Type x);
  19. void del(Type H[], int &n, int i);
  20. Type delete_max(Type H[], int &n);
  21. void print_heap(Type H[], int n);
  22. void make_heap(Type H[], int n);
  23. void heap_sort(Type H[], int n);
  24. void merge_heaps(Type A[], Type B[], int n);
  25.  
  26. void shift_up(Type H[], int i){
  27.         bool done = false;
  28.         while(i!=1){
  29.                 if(H[i]<=H[i/2]){
  30.                         break;
  31.                 }
  32.                 swap(H[i], H[i/2]);
  33.                 i /= 2;
  34.         }
  35. }
  36.  
  37. void shift_down(Type H[], int n, int i){
  38.         bool done = false;
  39.         while( (i=2*i)<=n ){
  40.                 if(i+1<=n&&H[i+1]>H[i]){
  41.                         i ++;
  42.                 }
  43.                 if(H[i/2]>=H[i]){
  44.                         break;
  45.                 }
  46.                 swap(H[i/2], H[i]);
  47.         }
  48. }
  49.  
  50. void insert(Type H[], int &n, Type x){
  51.         n++;
  52.         H[n] = x;
  53.         shift_up(H,n);
  54. }
  55.  
  56. void del(Type H[], int &n, int i){
  57.         Type x, y;
  58.         x = H[i], y = H[n];
  59.         n--;
  60.         if(i<=n){
  61.                 H[i] = y;
  62.                 if(y>=x){
  63.                         shift_up(H,i);
  64.                 }else{
  65.                         shift_down(H,n,i);
  66.                 }
  67.         }
  68. }
  69.  
  70. Type delete_max(Type H[], int &n){
  71.         Type x = H[1];
  72.         del(H, n, 1);
  73.         return x;
  74. }
  75.  
  76. void heap_sort(Type H[], int n){
  77.         make_heap(H,n);
  78.         for( int i = n; i>1; i--){
  79.                 swap(H[1],H[i]);
  80.                 shift_down(H,i-1,1);
  81.         }
  82. }
  83.  
  84. void print_heap(Type H[], int n){
  85.         for( int i = 1, j = 1; i<=n; i++){
  86.                 printf("%-4d",H[i]);
  87.                 if((i+1)%j==0){
  88.                         cout<<endl;
  89.                         j*=2;
  90.                 }
  91.         }
  92.         cout<<endl;
  93.         if(i%j)cout<<endl;
  94. }
  95.  
  96. void make_heap(Type H[], int n){
  97.         H[n] = H[0];
  98.         for( int i= n/2; i>=1; i--){
  99.                 shift_down(H,n,i);
  100.         }
  101. }
  102.  
  103. /*
  104. *      合并堆算法
  105. *
  106. *      输入：堆A，堆B，堆的长度n
  107. *      输出：由堆A和堆B合并成的新大顶堆C
  108. *
  109. *      该算法执行了2n次时间复杂度为O(log(n))的insert操作，故
  110. *      它的执行时间为O(n*log(n))
  111. *
  112. */
  113. void merge_heaps(Type A[], Type B[], Type C[], int n){
  114.         int i,k;
  115.         for(i=1, k = 0; i<=n; i++){
  116.                 insert(C, k, A[i]);
  117.         }
  118.         for(i=1, k = n; i<=n; i++){
  119.                 insert(C, k, B[i]);
  120.         }
  121. }
  122.  
  123. int main(){
  124.         int i,n;
  125.         Type A[N],B[N],C[2*N];
  126.  
  127.         /*      输入堆的元素 */
  128.         cout<<"请输入堆的元素个数：";
  129.         cin>>n;
  130.  
  131.         cout<<"请输入堆A的元素：";
  132.         for(i = 0; i<n; i++){
  133.                 cin>>A[i];
  134.         }
  135.  
  136.         cout<<"请输入堆B的元素：";
  137.         for(i = 0; i<n; i++){
  138.                 cin>>B[i];
  139.         }
  140.  
  141.         /*      建堆 */
  142.         make_heap(A,n);
  143.         make_heap(B,n);
  144.  
  145.         /*      打印堆*/
  146.         cout<<"大顶堆A："<<endl;
  147.         print_heap(A,n);
  148.  
  149.         cout<<"大顶堆B："<<endl;
  150.         print_heap(B,n);
  151.  
  152.         /*      合并堆 */
  153.         merge_heaps(A,B,C,n);
  154.  
  155.         /*      打印堆*/
  156.         cout<<"合并后的大顶堆C："<<endl;
  157.         print_heap(C,2*n);
  158.  
  159.         return 0;
  160. }
  • 无匹配
Small_feed 评论 (2)
1
[回复]
哈凌大侠 说:
2010年12月28日 03:07

博主，n个元素重新建堆也不过是O(N)的，哪能用O(nlogn)的算法合并堆呢？

2
[回复]
Head_small
YOYO 说:
2010年12月29日 23:42

这个算法本身是nlogn的

但是重建堆的方法比这样合并更优 嗯 表示很惭愧


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter