ヒープソート (Heap Sort)

配列を最大ヒープ化し最大値を末尾へ送るヒープソートを棒アニメーションで確認。O(n log n)+O(1)空間なのに使われない理由も解説します。

アルゴリズム

配列

サイズ48
比較中交換/書込ピボット/基準読み整列確定
速度50×

比較

0

交換/書込

0

ステップ

0/665

読み

0

補助メモリ

0

再帰の深さ

1/1

速度を落として「1ステップ」で疑似コードのハイライトと棒の色を見比べてみてください。 グレーの棒はヒープから取り出され確定した位置です。

疑似コード

build max-heap (siftDown n/2→0)

for end ← n−1 down to 1

swap a[0] ↔ a[end] // 최댓값 확정

siftDown(0, end)

// child = 2·i+1, 2·i+2 중 큰 쪽과 비교

// 부모 < 자식이면 교환하며 내려감

計算量

最良O(n log n)
平均O(n log n)
最悪O(n log n)
空間O(1)
安定×

ヒープソートは配列を完全二分木として扱い、親が常に子より大きい最大ヒープに整えた後、先頭の最大値を末尾と交換して確定し、残りでヒープ性を回復(sift-down)する処理を繰り返します。

ヒープ構築がO(n)、取り出しごとにO(log n)で全ケースO(n log n)、追加メモリO(1)のインプレースソートです。親子アクセス(2i+1)がキャッシュに悪く不安定なため実用は限られますが、優先度キューの中身としては標準です。 ソート可視化

よくある質問

ヒープとは何ですか?
親が子より常に大きい完全二分木(最大ヒープ)です。配列ならiの子は2i+1, 2i+2でポインタ不要です。
実際どこで使われますか?
メモリ制約が厳しい環境、最悪性能の保証が必要な場面、上位K個の抽出、優先度キューの内部実装です。

他のアルゴリズム