対象試験と出題頻度
ヒープソートは、応用情報技術者試験で出題されるテーマです。
整列アルゴリズムの比較問題として定番化しており、「クイックソート」「バブルソート」「シェルソート」「マージソート」との違いを正確に区別できるかが問われます。
H23秋期 応用情報 午前問6、H28秋期 応用情報 午前問6など、同一問題の流用も含めて複数回出題されています。
詳細をクリックして確認
応用情報技術者
★★☆☆☆
ランクC（応用）余裕があれば覚える
用語の定義
情報処理試験を勉強していると、「ヒープソートって結局何をしているの？」「クイックソートやマージソートと何が違うの？」と混乱しがちです。
ヒープソート（Heap Sort）とは、一言で言うと
「未整列データをヒープ（順序木）に構成し、根から最大値（または最小値）を取り出すことを繰り返して整列するアルゴリズム」
のことです。
イメージとしては、「トーナメント戦で毎回優勝者を決めて退場させる」こと。
参加者全員でトーナメントを組み、優勝者（最大値）を確定させて抜けてもらい、残りのメンバーで再びトーナメントを行う。これを全員が退場するまで繰り返すのがヒープソートの考え方です。
📊 ヒープソートの基本情報
| 項目 | 内容 |
|---|---|
| 英語名 | Heap Sort（heap＝山・積み上げ） |
| 分類 | データ構造利用型の整列アルゴリズム（内部ソート） |
| 平均計算量 | O(n log n) |
| 最悪計算量 | O(n log n) ※最悪でも性能が劣化しない |
| 安定性 | 不安定ソート（同一値の元の順序が保存されない） |
詳細解説
ヒープソートを理解するには、まず「ヒープ」というデータ構造を押さえる必要があります。
ヒープ（順序木）とは
ヒープとは、完全二分木の一種で「親ノードの値が常に子ノードの値以上（または以下）」というルールを持つ木構造です。親≧子のルールなら「最大ヒープ」、親≦子なら「最小ヒープ」と呼びます。
この構造のおかげで、根（ルート）には常に最大値（最大ヒープの場合）が位置します。
▶ ヒープの構造を図で確認（クリックで展開）
以下は、配列 [3, 5, 9, 6, 1, 2] を最大ヒープに構成した例です。
9
6
2
5
1
3
根（最大値）
根ノードに最大値 9 が配置されています。どの親子関係を見ても「親≧子」が成立しているのがポイントです。配列上では [9, 6, 2, 5, 1, 3] と格納されます（インデックス i の子は 2i+1 と 2i+2）。
ヒープソートの処理手順
手順は大きく2段階に分かれます。
▶ 手順を図解で確認（クリックで展開）
【段階1】ヒープ構築（heapify）
未整列の配列データを最大ヒープに変換します。末尾のノードから順に親子関係を修正し、全体が「親≧子」のルールを満たす木構造になるまで調整します。
【段階2】根の取り出しと再構築の繰り返し
根（最大値）を配列の末尾と交換し、末尾を「整列済み領域」として確定させます。残りの未整列領域を再びヒープに修正し、次の根（次に大きい値）を取り出す――これを要素が1つになるまで繰り返します。
▼ 処理の流れ（配列 [3, 5, 9, 6, 1, 2] の場合）
| ステップ | 操作内容 | 配列の状態 |
|---|---|---|
| 初期 | 入力データ | [3, 5, 9, 6, 1, 2] |
| 段階1 | 最大ヒープを構築 | [9, 6, 3, 5, 1, 2] |
| 1回目 | 根(9)と末尾(2)を交換 → 再ヒープ化 | [6, 5, 3, 2, 1 | 9] |
| 2回目 | 根(6)と末尾(1)を交換 → 再ヒープ化 | [5, 2, 3, 1 | 6, 9] |
| … | 同様に繰り返す | … |
| 完了 | 全要素が整列済み | [1, 2, 3, 5, 6, 9] |
※「|」の右側が整列済み領域
他の整列アルゴリズムとの比較
ヒープソートを正しく理解するには、他のアルゴリズムと「何を基準に整列しているか」で整理するのが近道です。
📊 主要な整列アルゴリズムの比較
| アルゴリズム | 手法の核心 | 平均計算量 | 最悪計算量 | 安定性 |
|---|---|---|---|---|
| ヒープソート | 順序木から最大値を取り出す | O(n log n) | O(n log n) | 不安定 |
| クイックソート | 基準値で大小のグループに分割 | O(n log n) | O(n²) | 不安定 |
| マージソート | 分割した部分列を併合しながら整列 | O(n log n) | O(n log n) | 安定 |
| バブルソート | 隣り合う要素を比較・交換 | O(n²) | O(n²) | 安定 |
| シェルソート | 一定間隔の部分列を整列し間隔を狭める | O(n^1.25)程度 | O(n²) | 不安定 |
ここだけは確実に押さえてください。ヒープソートは「順序木（ヒープ）を使って最大値を取り出す」点が他の手法と決定的に異なります。
クイックソートが「基準値による分割」、マージソートが「部分列の併合」、バブルソートが「隣接要素の交換」であるのに対し、ヒープソートは「木構造の活用」がキーワードです。
では、この用語が試験でどのように出題されるか見ていきましょう。
💡 ヒープソートの核心を3行で
・未整列データを完全二分木（ヒープ）に構成し、根から最大値を取り出して整列する
・平均・最悪ともにO(n log n)で、最悪ケースでも性能が劣化しないのが強み
・クイックソートは「基準値で分割」、バブルソートは「隣接要素の交換」と整理する
試験ではこう出る！
ヒープソートは、整列アルゴリズムの説明文を選ぶ問題として応用情報技術者試験で繰り返し出題されています。
出題パターンは大きく2つに分かれます。
📊 過去問での出題実績
| 試験回 | 出題内容 | 問われたポイント |
|---|---|---|
| AP H28秋 午前 問6 |
ヒープソートの説明として適切なものを選ぶ問題。4つの整列手法の説明文が並ぶ形式。 | ・「順序木にして最小値を取り出す」が正解 ・シェルソート・クイックソート・バブルソートの説明がひっかけ |
| AP H23秋 午前 問6 |
H28秋期と同一の問題構成。ヒープソートの説明を選ぶ。 | ・流用問題のため選択肢の構成も同一 ・同じキーワードで繰り返し出題されるパターン |
| AP R5秋 午前 問6 |
整列の過程（データ列の推移）を見て、使われたアルゴリズムを特定する問題。 | ・各アルゴリズムの「並び替えの特徴」から判別する力が必要 ・ヒープソートは選択肢として登場 |
📝 IPA試験での出題パターン
パターン1：「ヒープソートの説明を選べ」
4つの整列手法（シェルソート・クイックソート・バブルソート・ヒープソート）の説明文が並び、該当するものを選ぶ形式。キーワードは「順序木」「最小値（最大値）を取り出す」「未整列部分を縮める」。
パターン2：「データ列の推移から整列方法を特定せよ」
整列途中の配列の変化が図示され、どのアルゴリズムかを判定する形式。ヒープソートの場合、末尾側に大きい値が順に確定していく動きが見られるが、隣接交換（バブルソート）とは異なり非隣接の要素が入れ替わる点で区別する。
試験ではここまででOKです。ヒープ構築の具体的なコード実装まで午前問題で問われることはないので、深追いは不要です。
【確認テスト】理解度チェック
ここまでの内容を理解できたか、簡単なクイズで確認してみましょう。
Q. ヒープソートの説明として、最も適切なものはどれでしょうか？
- A. 中間的な基準値を決めて、それよりも大きな値を集めた区分と小さな値を集めた区分に要素を振り分け、それぞれの区分の中で同様な処理を繰り返す。
- B. ある間隔おきに取り出した要素から成る部分列をそれぞれ整列し、更に間隔を詰めて同様の操作を行い、間隔が1になるまでこれを繰り返す。
- C. 未整列の部分を順序木にし、そこから最小値を取り出して整列済の部分に移す操作を繰り返して、未整列の部分を縮めていく。
正解と解説を見る
正解：C
解説：
ヒープソートは、未整列データを順序木（ヒープ）に構成し、根から最大値または最小値を取り出して整列済み領域に移す操作を繰り返す手法です。「順序木」「最小値（最大値）の取り出し」がキーワードになります。
選択肢Aはクイックソートの説明です。基準値（ピボット）を使ってデータを2群に分割し、再帰的に整列する手法であり、木構造は使いません。選択肢Bはシェルソートの説明です。一定間隔おきの部分列を整列し、間隔を徐々に狭めていく手法であり、順序木とは無関係です。
よくある質問（FAQ）
Q. ヒープソートはクイックソートより速いですか？
平均的なケースではクイックソートの方が高速です。両者とも平均計算量はO(n log n)ですが、クイックソートはキャッシュ効率が良くメモリアクセスが局所的であるため、実測では定数倍の差で上回ります。一方、クイックソートは基準値の選び方が悪いと最悪O(n²)に劣化するのに対し、ヒープソートは最悪でもO(n log n)を保証します。「平均速度のクイックソート」「最悪保証のヒープソート」と整理してください。
Q. 「不安定ソート」とはどういう意味ですか？
同じ値を持つ要素が複数ある場合に、整列前の並び順が整列後に保存されないことを意味します。たとえば、成績が同点の2人 A さんと B さんが元の順序で A→B だったとしても、整列後に B→A になる可能性があります。安定ソートが必要な場面（元の順序を保ちたい場合）には、マージソートなどの安定ソートを選択します。
Q. ヒープソートは実務ではどこで使われていますか？
OSのタスクスケジューラやネットワークパケットの優先度制御など、「常に最大値・最小値を高速に取り出したい」場面で、ヒープソートの基盤であるヒープ構造が広く活用されています。完全な整列よりも「上位N件を高速に取得する」用途（部分ソート）に向いており、Pythonの標準ライブラリ heapq やJavaの PriorityQueue もヒープ構造を内部で使用しています。
Q. 配列でヒープを表現できるのはなぜですか？
ヒープは完全二分木であるため、要素が左詰めで隙間なく並びます。この性質を利用し、インデックス i のノードに対して「左の子＝2i+1」「右の子＝2i+2」「親＝(i-1)/2（切り捨て）」という計算式で親子関係を算出できます。ポインタを使った明示的な木構造が不要で、追加メモリなしに1つの配列上で整列処理が完結します。この「追加メモリが不要」である点を指して「内部ソート」と呼びます。
