STEP 8.2 ヒープ - 要素追加 上方移動で再構成

図4.15のヒープに、insert(9)を実行する。


<問題>



<実行例> 毎回の交換結果のヒープの内容をプリントしている。(この実行例でなくてもよい。交換の様子がわかるものは、もっとよい)

      
  1  2  3  4  5  6  7  8  9 10 11 12      (mainループからの呼び出し。insert前)
  4  7 16 32 25 95 18 81 59 38 42  0

  4
  7 16
 32 25 95 18
 81 59 38 42  0
                        ----------------------------------- この部分は、どこでプリントするかによります。
  1  2  3  4  5  6  7  8  9 10 11 12       (up_heapによる交換。6の95が12へ) 
  4  7 16 32 25 95 18 81 59 38 42 95

  1  2  3  4  5  6  7  8  9 10 11 12       (up_heapによる交換  3の16が6へ) 
  4  7 16 32 25 16 18 81 59 38 42 95
                        ------------------------------------ 同じにならなくてもよいです。下は同じはず (7.3)
  1  2  3  4  5  6  7  8  9 10 11 12
  4  7  9 32 25 16 18 81 59 38 42 95        (mainループからの呼び出し。(再構成)後 9は、3に)

  4
  7  9
 32 25 16 18
 81 59 38 42 95
 

<下の未完成プログラムを実行すると>

  1  2  3  4  5  6  7  8  9 10 11 12
  4  7 16 32 25 95 18 81 59 38 42  0

  4
  7 16
 32 25 95 18
 81 59 38 42  0


  1  2  3  4  5  6  7  8  9 10 11 12
  4  7 16 32 25 95 18 81 59 38 42  9

  4
  7 16
 32 25 95 18
 81 59 38 42  9   (up_heapが何もしないので、末尾に9が追加されただけ。ヒープの制約を満たさない。9の親は12/2=6で、95)





解答例

#include <stdio.h>
#define N 12  /* 11 + 1 */

void up_heap(int n); /* 課題です */
void insert(int x);
void print_heap(int n);
void print_tree_heap(int n);

int S[N+1]={0,4,7,16,32,25,95,18,81,59,38,42,0};

void print_heap(int n) {
   int i;

   for (i=1; i <= n; i++)
      printf("%3d", i);
   printf("\n");

   for (i=1; i <= n; i++)
      printf("%3d",S[i]);
   printf("\n");

   printf("\n");
}

void print_tree_heap(int n){
   int i, j;

   /* 2の累乗ごとに改行 */
   for (i = 1 ; i <= n; i = i*2) {
      for (j= i ; (j < i*2 && j <= n) ; j++)
         printf("%3d", S[j]);
      printf("\n");
   }
   printf("\n\n");
}


void up_heap(int n) {

     /* p.92, p93の疑似コードと解説を参考に実装 */
     /* STEP8.1も参考に */
}

void insert(int x){
   static int n = N-1;  /* 最初は11個 1-11番目まで */
   n++;
   S[n] = x;            /* 12番目にxを追加して */
   up_heap(n);          /* ヒープを再構成 */
}

int main(void) {
   int i;

   print_heap(N);  /* 最後尾には0 */
   print_tree_heap(N);

   insert(9);  /* 最後尾に9を追加し、ヒープを上方に再構成 */

   print_heap(N);
   print_tree_heap(N);

   return 0;
}