STEP 8.4　ヒープを使ったソート　ヒープソート

59
38
7
42
16
81
4
32
95
18
25　（WindowsではControl z   UNIXでは、Control d)
  1  2  3  4  5  6  7  8  9 10 11
 59 38  7 42 16 81  4 32 95 18 25

 59
 38  7
 42 16 81  4
 32 95 18 25　　　　　　　　　　　　（ただ、格納しただけなので、ぐちゃぐちゃ）


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

  4
 16  7
 32 18 81 59
 42 95 38 25　　　　　　　　　　　　　（ヒープとして再構成した結果）（図4.15とは異なる）

  1  2  3  4  5  6  7  8  9 10 11
 95 81 59 42 38 32 25 18 16  7  4      (ヒープソート後の配列）

• 上の文字列str中、２番目の動物を表示する。

解答例

#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の位置の親でよいか。ダメなら再構成 */
   }
}

/* heap sort */
void heap_sort (int S[], int n) { /* ヒープS, 要素n */
   int i;
  
  /*
   for(i = n; i >1 ; i--) {
      down_heap(S, 1, i);
      swap(&S[1], &S[i]);
   }
   */

   while (n > 1) { /* down heapの範囲を小さくしていく */
      swap (&S[1], &S[n]);
      n--;
      down_heap(S, 1, n); 
   }
}



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);   /* ヒープソート 要素はn個 */
   print_heap(S, n);  /* ソート結果として、プリントする */

   return 0;
}