ヒープソートとは？

ヒープソートとは、データからヒープ（親が子より必ず大きい、または必ず小さい木構造）を構成し、根にある最大値または最小値を取り出しては木を再構成する操作を繰り返して整列する方法。最悪でもO(n log n)で、追加の作業領域をほとんど必要としない点が特徴。

高度試験・午前I（全区分共通）の過去問では1回出題されています。

ひーぷそーと

高度試験・午前I（全区分共通）の頻出用語／午前I（全区分共通）

ヒープソートの意味

データからヒープ（親が子より必ず大きい、または必ず小さい木構造）を構成し、根にある最大値または最小値を取り出しては木を再構成する操作を繰り返して整列する方法。最悪でもO(n log n)で、追加の作業領域をほとんど必要としない点が特徴。

配列を最大ヒープにすると根が最大値になる。根と末尾の要素を交換して末尾を確定させ、残りを再びヒープに直す。この「取り出して整え直す」を繰り返すと、配列の後ろから大きい順に確定していき昇順に整列される。整え直しは木の高さ分＝log n回の比較で済む。

ヒープは「親と子」の大小関係しか保証せず、左右の子の間や兄弟間の順序は決まっていない。二分探索木のように「左<親<右」が成り立つと誤解しやすい。また不安定なソートである点も問われる。

ヒープソートの説明として、適切なものはどれか。
正解：未整列の部分を順序木にし、そこから最小値を取り出して整列済の部分に移す。この操作を繰り返して、未整列の部分を縮めていく。
要点：ヒープソートは順序木から最小値を取り出し続ける
ヒープソートは、未整列部分を親子の大小関係が保たれた順序木（ヒープ）として構成し、根にある最小値（または最大値）を取り出して整列済み部分へ移す操作を繰り返す。取り出すたびにヒープを再構成するため、計算量は最悪でもO(n log n)に収まる。
出典：平成28年度秋期高度共通_午前I試験 am1 問3（IPA）

最終更新：2026-08-25／解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。