ヒープソート

ヒープソートは、最大値をもっとうまく見つける選択ソートです。未整列の値をヒープに入れておきます。ヒープはリスト自体の中に格納された木で、最大値が常に一番上にあります。それを取り出してヒープを修復するのは、全体を走査しなくても約 log n ステップで済みます。

二分木として描かれたヒープと、その下に同じ値を表す棒。根にある最大値がリストの末尾と交換されている
二分木として描かれたヒープと、その下に同じ値を表す棒。根にある最大値がリストの末尾と交換されている

リストの中の木

二分ヒープはポインタの要らない木です。位置 0 が根で、位置 i の子は位置 2i + 1 と 2i + 2 です。つまり位置 1 と 2 が根の子、位置 3 から 6 が次の段、というように続きます。最後の段以外はすべて埋まっていて、最後の段は左から埋まります。最大ヒープではどの親も子以上の大きさなので、最大値は常に根にあります。

ふるい落とし

すべての作業を1つの操作で行います。値をふるい落とすには、その値を子と比較します。大きい方の子がその値より大きければ交換し、その値を新しい子と比較します。どの子も大きくないか、一番下に着いたら止まります。木の段数は約 log₂ n しかないので、1回のふるい落としは多くても約 2 log₂ n 回の比較です。

ヒープを作ってから整列

ヒープを作るには、最後の親から根までさかのぼりながら、各親をふるい落とします。各部分木は、その親がふるい落とされて入ってくる前にヒープになっています。次に整列です。根、つまり最大値をヒープの最後の値と交換します。その値は最終位置に確定します。ヒープは1つ短くなり、根に来た値をふるい落としてヒープを修復します。値が1つになるまで繰り返します。

例

5, 1, 4, 2, 8 で考えます。ヒープの構築では、1 が 8 の下へふるい落とされ、次に 5 が 8 の下へふるい落とされて、8, 5, 4, 2, 1 になります。ここで 8 が末尾と交換され、根に来た 1 が 5 と 2 を越えてふるい落とされます:5, 2, 4, 1 | 8。次に 5 が末尾に移り、1 が 4 を越えてふるい落とされます:4, 2, 1 | 5, 8。あと2回で整列が終わります:1, 2, 4, 5, 8。比較は12回、交換は10回です。

長所と短所

ヒープソートは最悪の場合でも n log n に比例する時間で済み、追加メモリも要りません。クイックソートは n² まで遅くなることがあり、マージソートはリストと同じ長さのバッファが必要なので、ヒープソートは安全な代替手段です。C++ 標準ライブラリで使われる introsort は、クイックソートの分割がうまくいかないとヒープソートに切り替えます。実際のコンピュータでは、リスト内の離れた位置の間を飛ぶため、たいてい両方より遅く、安定でもありません。J. W. J. Williams が1964年に、二分ヒープとともにヒープソートを発表しました。

試してみよう

アプリを開いて「ステップ」を押してください。棒の上の木がヒープを表します。ふるい落とされている値には専用の色が付き、比較している子は強調表示され、交換はすべて木と棒の両方に表示されます。ヒープが完成したら、根が末尾と交換され、緑になって木から抜ける様子を見てください。

よくある質問

ヒープソートの時間計算量は?

最良、平均、最悪のいずれの場合も O(n log n) です。ヒープの構築は O(n)、n − 1 回の取り出しはそれぞれ O(log n) です。追加メモリ O(1) のインプレースで並べ替えます。

ヒープソートと選択ソートの違いは?

どちらも残りの中で最大(または最小)の値を何度も取り出します。選択ソートは未整列部分を全部走査して見つけるので、毎回 n 回比較します。ヒープソートは未整列部分をヒープに入れておくので、最大値はすでに一番上にあり、ヒープの修復は約 log n 回の比較で済みます。

ヒープは並べ替え以外に何に使われますか?

優先度付きキューです。ヒープなら最大(または最小)の要素がすぐ得られ、要素の追加や削除も約 log n ステップでできます。スケジューラ、Dijkstra の最短経路アルゴリズム、イベントシミュレーションなどで使われています。

ヒープソートは安定ですか?

いいえ。根を末尾と交換すると値が遠くまで移動するので、等しい値どうしの順序が変わることがあります。

試してみますか?

ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。

ヒープソートを試す