ヒープソート
整列 バブルソート、選択ソートの演習
ヒープソートは「ヒープ : heap」という2分木構造を使ったソートアルゴリズムで、O(N log N) の計算量が保証され、メモリの使用効率も良い。
ヒープ構造そのものはソートのためだけのものではなく、データを管理保存する手法である。データの追加、削除が高速という特徴をもつ。よく似たバランスの取れた木（B木、AVL木）はデータベースシステムのアルゴリズムとして利用されている。
ヒープは２分木の一種で、一つのトップのデータノードが、右と左の二つの木（ヒープ）を持つ、再帰的なヒープ構造を持っている。
ヒープの条件は、注目するヒープのトップのデータが、そのヒープの最大値（もしくは最小値）である、ことである。
このため
ヒープのトップが最大値
左右の子ヒープのトップ二つはそれぞれの子ヒープの最大値なので、全体の２番目は、左右のトップのどちらか
という性質を持っている
新しいデータを追加するとき、既存のデータを削除するときに、この性質を保つようにする。この計算には O(log N) かかる。
配列によるヒープの表現
ヒープは二分木なのでリンクポインタで表現するのが自然だが、配列にも簡便に実装できる、という特徴がある。
トップのノードをa[1] とする。その左右の子ノードをa[2]、a[3] とする。
以下同じように
a[2]の子ノードとしてa[4]、a[5]
a[3]の子ノードとしてa[6]、a[7]
、、、
a[n]の子ノードとしてa[2n]、a[2n+1]
とすると、配列の中だけで無限にヒープを増やしていくことができる。
例えば次の並びはヒープになっている（すべてのnで a[n] > a[2n] かつa[n]>a[2n+1]）
a[1] a[2] a[3] a[4] a[5] a[6] a[7]
10 9 8 7 6 5 4
クイズ
a[1] からa[7]までの配列の親子関係がどうなっているか、親子を矢印で繋いだ図を描いてみよう
a[1]からa[7]までのヒープに 4〜10 の7つの数字を入れてヒープの条件を満足する並びは他にもあるので作ってみよう
ヒープを使ったソートのアルゴリズム
データをヒープとして格納する
トップのデータが最大値なのでそれを取り除き、別に保存する
落とし更新する
ヒープの右下（配列では添字が一番おおきなもの）をトップの位置に仮置きして注目データとする
注目データが左右の子より大きければヒープ条件が達成できているので、更新を終わる
注目データの左右の子を比べて、大きいほうと、注目データを入れ替える
（これによって、最大値がヒープのトップに来る。注目データは一つ「落ちる」）
落とした注目データを一段下のヒープの中で、同様に落としていく
ヒープが更新されたら、トップがつぎの最大値になっているので、頭に戻って繰り返す
こうして全てのデータをヒープから取り除いていくと、保存したデータは降順にならんでいる
ヒープを使ってのソートのプログラム
code:heapall.c
/* 準備中 */
再帰的なヒープの更新プログラの断片は次のように書ける
code: heap01.c
/* 配列a[]のうち size個のデータで、 an 以下のヒープがヒープの条件を満たすようにデータを落としていく */ downheap(int a[], int n, int size){
if(n*2 > size) return;
if(n*2+1 > size){
}else{
}
if(an >= m) return; // ヒープができている downheap(a, n*2, size);
}else{
downheap(a, n*2+1, size);
}
}
クイズ
ヒープができている状態からデータを減らしていくときに downheap を使う
新しいデータがいくつかあるとき、それをヒープにする（upheap）にはどうしたらいいか
演習
1）10個の数値を読み込み、配列中にヒープの条件を満たした形で格納するプログラム(upheap)を書こう
2）ヒープになった配列を使い、データを大きい順に並べるプログラムを書こう