ヒープソートとは？ひーぷそーと
ヒープソートとは、配列を親と子の大小関係だけを保つ木（ヒープ）に組み替え、根に来る最大値または最小値を取り出しては木を整え直す操作を繰り返して並べ替える方法。最悪でも O(n log n) を保証し、元の配列の中で入れ替えるだけなので追加の作業領域をほとんど使わない。
最終更新：2026-10-06
情報処理安全確保支援士を最短で暗記・合格する →背景
整列の代表であるクイックソートは平均こそ速いが、偏った入力では比較回数が n の二乗まで悪化する。応答時間に上限を約束したい処理や、外から与えられた入力を並べ替える処理では、最悪値が読めないことがそのまま危険になる。取り出す手間を木の高さで抑えるこの方法は最悪でも n log n を保ち、作業用の配列も余分に確保しないため、資源が限られた環境や、入力を攻撃者が選べる場面で選択肢になる。
具体例
Linux カーネルには、処理時間が入力の偏りで跳ねては困る箇所のために heapsort の実装が置かれている。手順は、まず配列全体を最大ヒープにし、根と末尾を交換して末尾を確定させ、残りを木の高さぶん（log n 回）の比較で整え直す、の繰り返しになる。後ろから大きい順に確定していき、結果として昇順に並ぶ。
試験での引っ掛け
ヒープが保証するのは親と子の関係だけで、兄弟どうしや左右の枝の間に順序は無い。二分探索木の「左＜親＜右」と同じつもりで読むと、根以外の位置から値を探せると誤解する。等しい値の元の並びも保たれない不安定な整列なので、安定性が要る処理には向かない。
関連用語
出典・参考
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。