ヒープソートとは何ですか？

二分ヒープというデータ構造を利用して最大（最小）値を効率的に取り出しながらソートするアルゴリズム。追加メモリ不要でO(n log n)を保証する。

ヒープソートのポイントは？

配列を二分ヒープ（親が子より大きい完全二分木）に変換してからソートする。最悪・平均ともにO(n log n)で、追加メモリO(1)のインプレースソート。不安定ソートだが、メモリ効率が非常に良い。優先度付きキューの実装にも使われるヒープの性質を活用している

【ひーぷそーと】

💡 「一番大きいのを取り出す」を繰り返すだけで全部並ぶ！

📌 このページのポイント

ヒープソートのイメージ → 二分ヒープのツリーと配列の対応

ひよこ

ヒープソートの「ヒープ」って何？

ペンギン先生

ヒープは「親が子より必ず大きい（または小さい）」というルールの完全二分木だよ。山のてっぺんに一番大きい値が来るイメージだね

ひよこ

それでどうやってソートするの？

ペンギン先生

まず配列全体をヒープに変換する。すると先頭に最大値が来るから、それを配列の末尾と交換する。で、残りの部分をまたヒープに直して最大値を取り出す…を繰り返すんだ

ひよこ

ペンギン先生

ヒープソートの最大の強みは「追加メモリがいらない」ことと「最悪でもO(n log n)が保証される」こと。クイックソートは最悪O(n²)だし、マージソートはO(n)の追加メモリが必要だからね

ひよこ

じゃあ最強じゃない？なんでクイックソートのほうが使われるの？

ペンギン先生

実は同じO(n log n)でも、ヒープソートはキャッシュ効率が悪いんだ。配列の離れた場所を頻繁にアクセスするから、CPU キャッシュにデータが乗りにくい。それでクイックソートに実測で負けることが多いんだよ

ひよこ

ヒープってソート以外にも使うの？

ペンギン先生

もちろん！優先度付きキュー（プライオリティキュー）はヒープそのものだよ。ダイクストラ法やイベント処理など「次に最も優先度が高いものを取り出す」場面では欠かせないデータ構造なんだね

まとめ：ざっくりこれだけ覚えればOK！

「ヒープソート」って出てきたら「ヒープ構造で最大値を取り出し続けるソート」と思えればだいたいOK！

📖 おまけ：英語の意味

「Heapsort」＝ヒープ（山）を使ったソート

💬 1964年にJ.W.J.ウィリアムズが考案したアルゴリズムだよ。「ヒープ」は木構造の頂上に最大値が来る「山」のイメージだね