ヒープソートとは？ひーぷそーと
ヒープソートとは、データからヒープ（親が子より必ず大きい、または必ず小さい木構造）を構成し、根にある最大値または最小値を取り出しては木を再構成する操作を繰り返して整列する方法。最悪でもO(n log n)で、追加の作業領域をほとんど必要としない点が特徴。
最終更新：2026-10-07
この語が出る過去問を解く →具体例
配列を最大ヒープにすると根が最大値になる。根と末尾の要素を交換して末尾を確定させ、残りを再びヒープに直す。この「取り出して整え直す」を繰り返すと、配列の後ろから大きい順に確定していき昇順に整列される。整え直しは木の高さ分＝log n回の比較で済む。
試験での引っ掛け
ヒープは「親と子」の大小関係しか保証せず、左右の子の間や兄弟間の順序は決まっていない。二分探索木のように「左<親<右」が成り立つと誤解しやすい。また不安定なソートである点も問われる。
関連用語
出た過去問
出典：平成28年度 秋期 高度試験 午前Ⅰ 問3（IPA）
ヒープソートの説明として、適切なものはどれか。
正解：未整列の部分を順序木にし、そこから最小値を取り出して整列済の部分に移す。この操作を繰り返して、未整列の部分を縮めていく。
要点：ヒープソートは順序木から最小値を取り出し続ける
ヒープソートは、未整列部分を親子の大小関係が保たれた順序木（ヒープ）として構成し、根にある最小値（または最大値）を取り出して整列済み部分へ移す操作を繰り返す。取り出すたびにヒープを再構成するため、計算量は最悪でもO(n log n)に収まる。
出典・参考
公式シラバスの1 基礎理論 ＞ 2. アルゴリズム ＞ (2) 代表的なアルゴリズムに掲載されている用語です。
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。