ヒープから最大要素を取り除く
次に、ヒープから最大要素を取り除く処理を考えましょう。ヒープの条件:「どの節においても 親 >= 子」から「root より大きな node は heap 内に存在しない」すなわち「root が heap 内の最大要素である」ことが明らかです。
まず、root と heap の末尾要素とを交換し、末尾に移された最大要素を heap から切り離します（fig-08）。
この操作によって root 値が変更されますから、root とその子との間でヒープ条件を壊すかもしれません。壊れた heap の修復を行いましょう。2つの子のうち大きい方と親とを比較し、親より大きい子（親＜子）であるならその親子を交換します。この処理も前述の「ヒープに要素を追加する」と同様、その交換によって子の値が小さくなり、さらにその下の親子の大小関係を狂わすかもしれませんから、「親 >= 大きい子 を満たすように交換」を繰り返します。最大要素を取り除き、heap を修復した結果をfig-09に示します。
ヒープソートのからくり
上で説明した2つの基本処理:「ヒープに要素を追加する」と「ヒープから最大要素を取り除く」を使って配列をソートすることができます。
int[] ar = { 5, 1, 3, 6, 7, 8, 9, 0, 2, 4 };
これを heap を使ってソートしてみましょう。
まず、初期状態では heap 内の要素数は 0 です。「|」より左をheap化された配列要素とすれば、arの初期状態は:
|5 1 3 6 7 8 9 0 2 4
となります。
heap化されていない要素、つまり|の直後にある要素を「ヒープに要素を追加する」に示した処理でheap内に組み入れていきます:
5|1 3 6 7 8 9 0 2 4
5 1|3 6 7 8 9 0 2 4
5 1 3|6 7 8 9 0 2 4
6 5 3 1|7 8 9 0 2 4
7 6 3 1 5|8 9 0 2 4
8 6 7 1 5 3|9 0 2 4
9 6 8 1 5 3 7|0 2 4
9 6 8 1 5 3 7 0|2 4
9 6 8 2 5 3 7 0 1|4
9 6 8 2 5 3 7 0 1 4|
これで配列の全要素がheapに納まりました。配列arのどの要素に対しても:
ar[i] >= ar[i*2+1], ar[i] >= ar[i*2+2]
を満たしています。これでheapの作成は完了です。
次に「ヒープから最大要素を取り除く」に示した処理を繰り返します。
9 6 8 2 5 3 7 0 1 4|
から最大要素すなわちar[0]を|の直後に追い出し、heapを修復すれば:
8 6 7 2 5 3 4 0 1|9
となります。修復後のheapに対してもやはり最大要素はar[0]ですから、この処理をheapが空になるまで繰り返せば:
7 6 4 2 5 3 1 0|8 9
6 5 4 2 0 3 1|7 8 9
5 2 4 1 0 3|6 7 8 9
4 2 3 1 0|5 6 7 8 9
3 2 0 1|4 5 6 7 8 9
2 1 0|3 4 5 6 7 8 9
1 0|2 3 4 5 6 7 8 9
0|1 2 3 4 5 6 7 8 9
|0 1 2 3 4 5 6 7 8 9
となり、ご覧のとおり昇順のソートが完了しました。
heapに要素を追加する/最大要素を取り除く の2つの処理はheap内の節を 子から親 あるいは 親から子 へとたどる操作を繰り返します。最大の繰り返し回数は最も深い子からrootまでに通過する節の個数ですから要素数Nの「2を底とした対数」log2(N)となり、処理に要する時間はlog(N)に比例します。これらの処理をN回繰り返すことでソートが完了するのですから、ヒープソートの所要時間はN･log(N)に比例します。要素の大小関係だけを頼りに行うソートはどんなアルゴリズムであってもN･log(N)より速くはならないことが証明されているので、ヒープソートは最速のソートに属します。
