【ひーぷそーと】
ヒープソート とは？
最終更新:
💡 ヒープの最大値を、末尾へ順に確定
二分ヒープを使い、最大値などを順に取り出して並べるソート手法。配列内でヒープを保つ一般的な実装は、最悪O(n log n)の時間とO(1)の追加領域で動作する。
📌 このページのポイント
ひよこ ヒープソートの「ヒープ」って何？
ペンギン先生 ひよこ それでどうやってソートするの？
ペンギン先生 ペンギン先生 配列内で処理する一般的なヒープソートは、追加領域O(1)で最悪O(n log n)だよ。「メモリを一切使わない」という意味ではない。比較する際は、最悪時間だけでなく、同じキーの順序を保つ必要があるか、使える領域はどれくらいかも考えよう
ひよこ 最悪時間が良ければ、いつでも最速なの？
ペンギン先生 計算量は、あらゆる入力や環境での実行時間ランキングではないよ。要素数、比較のコスト、実装などで時間は変わる。また、一般的なヒープソートは不安定なので、同じキーの元の順序を保ちたい場合には別の方法も検討しよう
ひよこ ヒープってソート以外にも使うの？
まとめ：ざっくりこれだけ覚えればOK！
「ヒープソート」って出てきたら「ヒープ構造で最大値を取り出し続けるソート」と思えればだいたいOK！
📖 おまけ：英語の意味
「Heapsort」 ＝ ヒープを使ったソート
💬 1964年にJ. W. J. Williamsが「Algorithm 232: Heapsort」として発表した手法だよ。heapは「積み重なったもの・山」という意味で、ソートでは親と子に大小のルールを持つ構造を使うんだ