ヒープソートとは？ひーぷそーと
ヒープソートとは、データをヒープ（親が子より必ず大きい、または必ず小さいという決まりの木構造）に組み立て、根にある最大値を取り出しては残りを再びヒープに整え直す操作を繰り返す整列方法である。取り出しは1回あたり木の高さぶんの比較で済むため、データがどう並んでいても、データが増えたときの処理時間の伸び方（計算量）はO(n log n)で、O(n²)のように急に伸びることはない。作業用の配列を別に用意しなくてよい点も特徴。
最終更新：2026-10-09
基本情報を最短で暗記・合格する →背景
クイックソートは平均は速いが並びによっては最悪O(n²)に落ち、マージソート（半分に分けて整列したものを合わせていく方法）は最悪でも速いが同じ大きさの作業領域を別に要する。この2つの弱点を同時に避ける、つまり「最悪でもO(n log n)」と「追加領域ほぼゼロ」を両立させる方法として1964年にJ. W. J. Williamsが考案したのがヒープソートである。基本情報技術者試験では各ソートの計算量と安定性（同じ値どうしの元の並び順が保たれるか）の対応表、ヒープの性質の理解が問われる。
具体例
配列[3,9,1,7]を最大ヒープに組むと、3と9を入れ替え、さらに3と7を入れ替えて[9,7,1,3]になり、根は9。9を末尾の3と交換して9の位置を確定し、残り[3,7,1]を整え直すと[7,3,1]（7が根）。次は7を末尾の1と交換して確定し、残り[1,3]を整え直すと[3,1]。3と1を交換して[1,3,7,9]になり、後ろから大きい順に埋まる。JavaのPriorityQueueやPythonのheapqが同じヒープ構造を使っている。
試験での引っ掛け
ヒープは「親と子の大小」しか決めておらず、左の子と右の子の順序は決まっていない。二分探索木の「左＜親＜右」と混同すると、ヒープの図から要素の順序を読む問題を落とす。また根と末尾を交換するため、同じ値の順序が保たれない不安定なソートである点も対応表で問われる。
関連用語
出典・参考
公式シラバスの1 基礎理論 ＞ 2. アルゴリズム ＞ (2) 代表的なアルゴリズムに掲載されている用語です。
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。