ヒープソートとは？

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

ひーぷそーと

基本情報技術者試験の頻出用語／テクノロジ系

ヒープソートの意味

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

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

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

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