ヒープソート（Heap Sort）は、ヒープ（親が子より常に大きい/小さい木構造）を使い、最大値（または最小値）を取り出しては並べていくソートアルゴリズムです。
| 観点 | ヒープソート |
|---|---|
| 計算量（最悪も） | （保証） |
| 追加メモリ | 不要（in-place） |
| 安定性 | 不安定 |
| 強み | 最悪保証＋省メモリ |
データをいったんヒープに構築し、根（最大値）を取り出して末尾に置く操作を繰り返します。クイックソート と違い最悪でも を保証し、マージソート と違い追加メモリが不要なため、リアルタイム性が求められる場面や組込みシステムに適します。
試験では 「ヒープ構造を使う」「最悪も 」「追加メモリ不要」の 3 点が他のソートとの区別ポイントです。
