ヒープソートとは
ヒープソート（Heap Sort）とは、「ヒープ」と呼ばれる親子間の値に一定の大小関係ルールがある木構造を利用して、データを並べ替えるアルゴリズムです。ヒープの根（一番上）には必ず最大値（または最小値）が配置されるという特徴を利用し、根にある最大値を取り出して配列の末尾に移動させ、残りのデータで再びヒープを再構築する操作をデータがなくなるまで繰り返します。
具体例
バラバラに積まれた複数の箱から、最も重い箱（最大値）を取り出して並べていきます。取り出したあと、残された箱の山から自動的に「次に最も重い箱」が一番上に上がってくる仕組みをヒープで実現し、ソートを行います。
1. 未整理データからヒープ構造を作成（根に最大値がくる）
2. 根の最大値を取り出して、整理済み配列の末尾に移動
3. 残ったデータでヒープを再構築し、再度根から最大値を取り出す
4. 2〜3を全データ分繰り返してソート完了もう少し詳しく
ヒープソート（Heap Sort）は、木構造の一種である「ヒープ（特に最大ヒープ）」を用いて、効率的に整列を行うアルゴリズムです。手順は大きく分けて2つのフェーズからなります。まずヒープ構築フェーズでは、ソート対象の配列全体を、親ノードの値が子ノードの値以上になる「最大ヒープ」構造に並べ替えます。この段階で、配列の先頭（ヒープの根）には全体の最大値が位置することになります。次にソートフェーズでは、根にある最大値（配列の先頭要素）と、未整列部分の末尾要素を入れ替えます。これにより、最大値が配列の末尾に確定します。次に、残された未整列部分（サイズが1減った配列）に対して、再度根からヒープ構造を再構築（ヒープ化）します。これにより次に大きい値が根に浮上します。この「最大値の確定とヒープ再構築」を、未整列部分の要素がなくなるまで繰り返します。ヒープソートは、最悪・最良・平均すべてのケースで時間計算量が O(N log N) となり、マージソートと違って追加のメモリ領域を必要としない（インプレースで動作する、領域計算量 O(1)）という優れた長所を持っています。しかし、同値の要素の順序が維持されない「不安定ソート」であり、またメモリ上の離れた位置にある要素を頻繁に入れ替えるため、キャッシュメモリの有効利用（参照の局所性）が効きにくく、実質的な実行速度はクイックソートよりも遅くなる傾向があります。
試験でのポイント
試験では、ヒープソートの時間計算量（O(N log N)）および領域計算量（追加メモリ不要の O(1)）に関する知識問題が出題されます。また、ヒープ構造を構築する手順や、要素を取り除いたあとの再構築（ヒープ化）の過程をトレースする問題が頻出です。マージソート（O(N log N)だが追加メモリが必要）やクイックソート（平均O(N log N)だが最悪O(N^2)）との特徴の違いを対比させて正しく説明できるように整理しておくことが重要です。
関連する用語
最大ヒープ（親ノードの値が子ノードの値以上であるヒープ）、キャッシュメモリ（CPUとメインメモリの間でデータを高速にやり取りするメモリ）、参照の局所性（プログラムが近いメモリ領域に繰り返しアクセスする特性）。