配列を最大ヒープ化し最大値を末尾へ送るヒープソートを棒アニメーションで確認。O(n log n)+O(1)空間なのに使われない理由も解説します。
アルゴリズム
配列
比較
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)がキャッシュに悪く不安定なため実用は限られますが、優先度キューの中身としては標準です。 ソート可視化