アルゴリズム・データ構造図鑑 · 基礎から応用へ

ヒープソート:最大値を取り出して末尾を確定する

最大ヒープの構築と取り出しを追い、構築が線形時間になる理由と安定性の限界を理解する。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. ヒープは全体を整列した配列ではない
  2. 4、1、3、2から取り出す
  3. 下から作るとO(n)になる
  4. 領域と安定性を確認する
  5. この記事をロゲイアに質問する理解を確かめる

ヒープは全体を整列した配列ではない

昇順にするヒープソートでは最大ヒープを作ります。親のキーが子以上であれば根が全体の最大値になりますが、兄弟や別の部分木同士の大小順は決まっていません。配列の添字を0から始めるなら、位置iの子は2i+1と2i+2です。根と未確定部分の末尾を交換して最大値を確定し、ヒープの対象範囲を一つ縮めます。交換後に根へ来た値を子と比べながら下げる操作をsift-downと呼びます。整列済みの末尾はヒープに含めません。

4、1、3、2から取り出す

[4,1,3,2]を下の内部節点から調整すると[4,2,3,1]という最大ヒープになります。根4と末尾1を交換し、残る[1,2,3]を調整すると[3,2,1,4]です。次に3を未確定範囲の末尾と交換し、根を調整して[2,1,3,4]へ進みます。最大値を取り出すたびに末尾の確定範囲が左へ広がります。配列の長さを変える必要はなく、ヒープの有効長を別に管理すれば同じ配列内で完結します。

下から作るとO(n)になる

各要素を一つずつ挿入してヒープを作る方法にはO(n log n)の上界がありますが、下からsift-downする構築はO(n)です。深い位置にある多数の節点は短い距離しか下がれず、高い位置の節点は少数しかないためです。高さhの節点数が概ねn/2^(h+1)以下になることを使うと、移動距離の総和は線形に抑えられます。その後の取り出しは高々n回で、一回O(log n)ですから全体の最悪時間はO(n log n)です。

領域と安定性を確認する

反復的にsift-downする標準版は、整列配列とは別にO(1)の補助領域で実装できます。ただし再帰実装なら呼び出しスタックも数える必要があります。離れた要素の交換により同じキーの出現順が変わるので、通常は安定ではありません。配列上の参照位置が飛びやすく、逐次的にマージする方法と実際のキャッシュ効率が同じとも限りません。空ヒープや一要素の境界、片方の子しかない節点、重複キーを検証し、比較関数の一貫性を前提にします。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 10

学習コースから次を選ぶ