解答例

#include <stdio.h>
#define N 30

void down_heap(int S[], int k, int r);
void make_heap(int S[], int n); /* Sの要素nまでをヒープに構成 */
void heapsort(int S[], int n); /* Sの要素nまでをヒープソートする */

void swap(int *x, int *y);
void print_heap(int S[], int n);
void print_tree_heap(int S[], int n);

/* 定番 swap。アドレス渡し。値を入れ替える */
/* 必要ならどうぞ */
void swap(int *x, int *y) {
   int tmp;
   tmp = *x;
   *x = *y;
   *y = tmp;
}

/* ヒープ配列をnまでプリントする */
void print_heap(int S[], 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");
}

/* ヒープを階層的にnまで、プリントする */
void print_tree_heap(int S[], 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");
}

/* 親 k に注目。rまでのヒープを下方に再構成 */
void down_heap(int S[], int k, int r){
   int i, j, v;
   v=S[k];  /* 最上位の親の値 vは最後まで変わらないので注意 */
   i=k;     /* 親 i 一番最初は最上位 下ではiの位置にvがあってよいのかをチェック する */
   j=2*k;   /* 子 j */

   while(1){
      if(j < r && S[j] > S[j+1]) {  /* ２つの子の比較。右の子の値が小さいとき */
         j++; /* 右の子を親と比較するためにセット */
      }

      if(j <= r && v > S[j]) {
      /* このiの位置にvをもってきたとしたら親の方が大きい。vはここより下でなければ */
         S[i]=S[j]; /* そこで、子の値を親にもちあげる */
         i=j;       /* 子のインデックスを親のインデックスに */
         j=2*j;     /* その親の子へ。これら２つの操作が、下へ向かっていることに 対応 */
    /*   print_heap(N-1);  ヒープの状況をプリントする */
      } else {
         break;    /* vが子より小さい。このiの位置にvがあるべきだ。whileループを飛び出す */
      }
   }
   S[i]=v; /* ここで最上位の親の値を最後に代入 */
}


/* down_heapを繰り返して、ヒープを構成する */
void make_heap (int S[],  int n) {
   int i;
   for (i = n/2 ; i >= 1; i--) {
      /* 最後の親から末尾までを構成。次第に前へ進む */
      /* 教科書のn-2(このプログラムではn-1)でもいいが、たぶんミス */
      down_heap(S, i, n); /* iの位置の親でよいか。ダメなら再構成 */
   }
}


int main(void){
   int n;
   int S[N]; /* Nは最大の要素数 教科書に従い、今回はローカル変数 */

   /* お決まりの配列はおもしろくないので、n個、入力する */
   /* EOF は、WIndowsではControl z, UNIXでは Control d */
   n = 1;
   while (scanf("%d", &S[n]) != EOF)
      n++;

   n = n - 1;    /* 読み取った要素の数 ここまでをヒープとみる */

   print_heap(S, n);
   print_tree_heap(S, n);   /* プリントする この段階ではぐちゃぐちゃ */

   make_heap(S, n); /* ヒープに構成する */
   print_heap(S, n);
   print_tree_heap(S, n);  /* ヒープ完成 */

   /* heap_sort(S, n);   ヒープソート */
   /* print_heap(S, n);  ソート結果として、プリントする */

   return 0;
}
STEP 8.3 ヒープを構成する

STEP 8.3　ヒープを構成する
