ヒープソート

ヒープソート

　ヒープソートも、『栢木先生の基本情報技術者教室』の説明では分かるわけがないです。
　最初の「未整列の部分を順序木に構成し、そこから最大値又は最小値を取り出して既整列の部分に移します。これらを繰り返して、未整列部分を縮めて整列を行う方法です。」までは分からないにしても間違いではありません。
　でも、ここからがいけません。「配列にする時には根を1、左の節は2×1、右の節は2×1+1とします。」というのも間違いではありませんが、これは枝構造になる親と、2つの子との位置関係を表しただけです。例えば配列にする時に、d[1]から始まる配列の場合、親の添え字がxであれば、子は(2x)(2x+1)が添え字になります。このような三角形にデータを並べて、ヒープ構造を形成していきます。

　説明に入ると、「では、データを整列してみましょう。」で、いきなり、「①木の根T(1)の値と、木の最後の節（整列対象の最後の要素に対応する節）の値と交換します。」になります。これは最初のヒープ木を作るまでの途中経過が一切なしで、いきなりヒープ木が完成してからの説明なので、なんでこれで整列ができるの ??? です。
　栢木先生の例では、最初に与えられたデータが、与えられた順番で配列にデータを配置するだけで既にヒープ木になっているので、いきなりこんな交換をしてもデータが崩れません。ですが普通は、でたらめの順番のものを並べ替えるのがソートというものですから、交換の前にヒープ木を作る並べ替えをしないで、いきなりこんな交換をしても全く意味はありません。
　ここ以降、②からは栢木先生の説明の通りです。

まずヒープ構造を作る

　ヒープソートをするには、まず準備段階として、ヒープ木の構造を作らないといけません。ヒープ木とは、親から3角形に下に子ども2つを順々に下に並べていったような構造で、子どもより親の方が値が大きくなるよう（昇順に整列する場合）にデータを並べたものです。（ヒープ木のイメージについては、参考書などで確認してください。説明は分からなくても、こんなイメージのものだくらいなら、そこら辺の参考書で分かります。）
　まずデータを、与えられた順に、d[0],d[1],d[2],d[3]…d[f-1]と格納します（fがデータ数）。それを

　上の図では、d[3] > d[7] 、d[2]>d[5] かつ d[2]>d[6]、の様になるように子と親とを入れ替えて整列し直します。同じように下から順次、全部の親が子よりも大きくなるように並べ替えると、 d[0]に、このデータの中で最大の値が上がってきます。（途中の入れ替えによって、その下にある子とのヒープ関係が崩れた場合には、こんどはまた下に向かって、入れ替えが無くなるまで、並べ替えをしておかないといけません。）
　これで初めのヒープ木が完成です。

最大値を最後に置いて、残りでまたヒープ木を作る

　ここで初めて栢木先生の説明①になります。
　上の並べ替えで出来た、ヒープ木の親になっているd[0]の最大値を、データの一番最後、この図ではd[7] と交換します。それで、d[7] は位置確定です。d[0]の値が変わってしまったので、今度はデータ数を1減らして、d[6]までの中で、ヒープ木を再構成します。それで、一番上のd[0]にまた、d[7]の次に大きい値が上がってくるので、これと、d[6]とを交換して、d[6]を確定します。
　同じようにして、どんどん大きい値を確定していって、データ数を減らしながら、最後に残るd[0]まで順次データを並び替えていくのが、ヒープソートです。

プログラムを作るにはもうちょっと大変

　上の説明では、ヒープ木の構造になるように並べ替えていく手順の説明を端折ってしまいました。
　実際のプログラムでは、配列d[0]だけの状態から初めて、扱うデータをd[1]、d[2]と一つずつ追加していきながら、追加したデータより親が小さい場合には、データを親と交換していきます。
　ただしそのデータ交換によって、今度は、交換した親と、さらにまたその親とのヒープ関係が崩れることもあるので、交換があった場合には、交換したデータのさらにその親とのデータの大小関係をどんどん比較していって、交換が無くなるところまでさかのぼっていかなければなりません。
　実際に動くプログラムを考えようとすると、プログラミング初心者にはなかなか難しい問題かもしれません。
　上の写真、　『令和2年度秋期 かんたん合格 基本情報技術者過去問題集　必勝対策問題午後 問6 P116』（平成30年度 春 午後問8）に、ちょうど、このヒープソートのプログラム例が載っています。

ヒープソートについて分かる解説書は皆無

　基本情報の参考書の中で、ヒープソートについて、午後のアルゴリズムなどの本ではなくて、きちんと分かる説明をしてくれている参考書は皆無です。『栢木先生の基本情報技術者教室』は、せっかく、他書などよりもかなり詳しく説明を試みてくれているわけですから、もう少し一番重要なポイントを押さえた説明をしてほしかったところです。

プログラムを組んでみた

　平成30年度 春 午後問8 の例を基にして、Cでプログラムを作ってみました。
　あまり点検ができてはいないので、もしかしたら、おかしげなところがまだあるかもしれません。一応、下の表示例の様には動いています。

ヒープソート（平成30年度 春 午後問8）

#include <stdio.h>
void heapSort(int data[], int num);
void makeHeap(int heap[], int num);
void downHeap(int heap[], int hlast, int num);

int parent(int i);
int lchild(int i);
int rchild(int i);
void swap(int *x, int *y);
void hyouji(int data[], int num, const char coment[]);

int main() {
  int data[] = { 60,5,45,15,30,10,20 };
  int num; /* データ数 */

  num = sizeof data / sizeof data[0];
  hyouji(data, num, "◎元データ");
  heapSort(data, num);
}

void heapSort(int heap[], int num) {
  int last;
  makeHeap(heap, num);

  for (last = num - 1; last > 0; last--) {
    swap(heap, heap+last);
    downHeap(heap, last - 1, num);
  }
  hyouji(heap, num, "◎ソート終了");
}

void makeHeap(int heap[], int num) {
  int i, k;
  for (i = 1; i < num; i++) {
    k = i;
    while (k > 0) {
      if (heap[parent(k)] < heap[k]) {
        swap(heap+parent(k), heap+k);
        k = parent(k);
      }else
        break;
    }
  }
  hyouji(heap, num, "◎ヒープ完成");
}

void downHeap(int heap[], int hlast, int num) {
  int n, tmp;
  n = 0;
  while (lchild(n) <= hlast) {
    tmp = lchild(n);
    if (rchild(n) <= hlast) {
      if (heap[tmp] <= heap[rchild(n)])
        tmp = rchild(n);
    }
    if (heap[tmp] > heap[n]) {
      swap(heap+tmp, heap+n);
    }else
      return;
  }
}

int parent(int i) {
  i = (i - 1) / 2;
  return i;
}

int lchild(int i) {
  i = i * 2 + 1;
  return i;
}

int rchild(int i) {
  i = i * 2 + 2;
  return i;
}

void swap(int *x, int *y) {
  int tmp;
  tmp = *x;
  *x = *y;
  *y = tmp;
}
void hyouji(int data[], int num, const char coment[]) {
  int i;
  printf("%s\n", coment);
  for (i = 0; i < num; i++) {
    printf("data[%d]= %d  ", i, data[i]);
  }
  printf(" \n");
}

出力結果

◎元データ
data[0]= 60  data[1]= 5  data[2]= 45  data[3]= 15  data[4]= 30  data[5]= 10  data[6]= 20
◎ヒープ完成
data[0]= 60  data[1]= 30  data[2]= 45  data[3]= 5  data[4]= 15  data[5]= 10  data[6]= 20
◎ソート終了
data[0]= 5  data[1]= 10  data[2]= 15  data[3]= 20  data[4]= 30  data[5]= 45  data[6]= 60