ヒープソート

ヒープソートは配列を最大ヒープに変え、最大値を末尾へ移す操作を繰り返します。最大ヒープでは、親の値が子の値以上です。根には現在の最大値があるため、全要素を探さずに次の値を取り出せます。

ヒープは配列内に置きます。このレッスンの時間の上界は O(n log n)、追加領域は O(1) です。離れた位置を交換するため、同値の要素の順序は保証しません。

ヒープソートの仕組み

添字は 0 から始まります。位置 i の左の子は 2i + 1、右の子は 2i + 2 です。ヒープのサイズ以上の添字には子がありません。

まず floor(n / 2) − 1 から 0 へ進み、各親を下へ移す sift-down を行います。両方の子があれば大きい方を選び、親より大きい場合に交換します。移動先でも同じ処理を続け、子がないか、親が子以上になったら終了します。

下から構築するのは、親を処理するときに左右の部分木をヒープにしておくためです。葉には処理が要りません。

構築後、根と未整列区間の末尾を交換します。末尾の最大値は確定し、ヒープのサイズを一つ減らします。新しい根から sift-down して最大ヒープを復元します。右側の確定済み領域は、以後の比較から外します。

ヒープソートのステップ

初期入力は [38, 12, 56, 7, 41, 23, 5] です。

ヒープの構築。 最後の親は添字 2 です。値 56 は子の 23 と 5 より大きいので、そのままです。添字 1 の 12 は、大きい子の 41 と交換します。配列は [38, 41, 56, 7, 12, 23, 5] になります。根の 38 は、大きい子の 56 と交換します。移動先の子は 23 と 5 なので停止します。最大ヒープは [56, 41, 38, 7, 12, 23, 5] です。三回の sift-down で二回交換しました。

56 の確定。 根の 56 と末尾の 5 を交換し、ヒープのサイズを 6 にします。根に来た 5 は 41 と交換し、次に 12 と交換します。ヒープは [41, 12, 38, 7, 5, 23]、確定済みの末尾は 56 です。

残りの抽出。 次は 41 を末尾へ移します。その後も 38、23、12、7 の順に確定します。毎回、交換で根に来た値を必要な位置まで下げます。最後に残る 5 は最小値です。結果は [5, 7, 12, 23, 38, 41, 56] になります。

木の表示と配列の表示は同じ要素を表します。根と末尾の交換、ヒープの縮小、根からの復元を分けて追うと、一回の抽出の役割が分かります。

時間・空間計算量

下からの構築は O(n) です。多くのノードは葉に近く、短い距離しか下がりません。各ノードが最大の高さを移動すると数える O(n log n) は、構築に対して過大な見積もりです。

抽出は最大 n − 1 回で、一回の sift-down は O(log n) 以下です。全体の上界は O(n log n) になります。ただし、全要素が同値なら比較で早く停止するため、どの入力でも同じ回数の処理を行うわけではありません。

sift-down はループで実装しており、再帰スタックも補助配列も使いません。追加領域は O(1) です。配列内を離れて参照するため、連続した要素を読む手法よりキャッシュ効率が下がる場合があります。

境界条件

• 空配列・一要素：構築や抽出の交換は不要です。
• 降順：最大ヒープの条件を満たします。プリセット [56, 41, 38, 23, 19, 12, 7] の構築では交換しませんが、昇順にする抽出は必要です。
• 昇順：小さい親を下げる処理が構築中に起こります。時間の上界は変わりません。
• 重複値：同値の親子は交換不要です。ただし、根と末尾の交換などで同値の順序が変わるため、安定ではありません。

よくある間違い

• 根から順にヒープを構築する：子の部分木が未完成だと、後の処理で親子関係が崩れます。最後の親から始めます。
• 抽出後も元のサイズを使う：確定済みの末尾をヒープへ戻してしまいます。
• 常に左の子と交換する：右の子が大きい場合、最大ヒープの条件を満たせません。
• 子の添字を 2i と 2i + 1 にする：それは 1 始まりの式です。この配列は 0 始まりです。
• 末尾が 0 になっても抽出を続ける：一要素のヒープは整列済みです。自身との交換は不要です。