ヒープとは？ひーぷ
ヒープとは、データ構造としてのヒープは、「親の値が必ず子の値以下（または以上）」という条件だけを満たす完全2分木。根に最小値（最大値）が来るので優先度付きキューの実装や整列に使う。挿入も取り出しも木の高さぶんで済み、計算量はO(log n)。
最終更新：2026-10-07
この語が出る過去問を解く →背景
最小値だけを次々に取り出したい場面——イベント駆動シミュレーションの次イベント選択、ダイクストラ法の次ノード選択、OSのスケジューリング——では、全体を完全に並べ替えるのは過剰な仕事になる。順序の保証を「根が最小」の1点だけに絞れば、更新の手間が木の高さぶんに収まる。完全2分木なので配列にそのまま詰められ、添字iの子が2iと2i+1という計算だけで親子をたどれるのも実装上の利点。
具体例
ヒープソートは、全データからヒープを構成し、根を取り出しては残りを再構成する操作を繰り返す整列法。最悪でもO(n log n)で、平均は速いが最悪でO(n²)まで悪化しうるクイックソートと対比して問われる。
試験での引っ掛け
同じ「ヒープ」でも、プログラム言語の記憶域では実行時に動的確保・解放されるメモリ領域（ヒープ領域。対になるのはスタック領域）を指す別概念で、ガベージコレクションの文脈ならこちら。データ構造のほうは2分探索木とも違い、保証されるのは親子間の大小だけで、左右の子や兄弟の間に順序は無い。したがって中間順（通りがけ順）に走査してもソート済みの列は得られない。
関連用語
出た過去問
出典：平成28年度 秋期 高度試験 午前Ⅰ 問3（IPA）
ヒープソートの説明として、適切なものはどれか。
正解：未整列の部分を順序木にし、そこから最小値を取り出して整列済の部分に移す。この操作を繰り返して、未整列の部分を縮めていく。
要点：ヒープソートは順序木から最小値を取り出し続ける
ヒープソートは、未整列部分を親子の大小関係が保たれた順序木（ヒープ）として構成し、根にある最小値（または最大値）を取り出して整列済み部分へ移す操作を繰り返す。取り出すたびにヒープを再構成するため、計算量は最悪でもO(n log n)に収まる。
出典：平成28年度 秋期 高度試験 午前Ⅰ 問6（IPA）
プログラム実行時の主記憶管理に関する記述として、適切なものはどれか。
正解：プログラムが使用しなくなったヒープ領域を回収して再度使用可能にすることを、ガーベジコレクションという。
要点：GCは参照されなくなったヒープ領域を自動回収する
ガーベジコレクションは、プログラムが動的に確保したヒープ領域のうち、どこからも参照されなくなった領域を自動的に検出して回収し、再利用可能にする仕組みである。解放漏れによるメモリリークを防げる一方、回収処理のために実行が一時停止することがある。
出典・参考
公式シラバスの1 基礎理論 ＞ 4. プログラム言語 ＞ (3) プログラム言語の記憶域に掲載されている用語です。
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。