ヒープ 【heap】
概要
ヒープ(heap)とは、データ構造の一種で、木構造(ツリー構造)のうち、親要素が子要素より常に大きい(あるいは小さい)という条件を満たすもの。また、コンピュータプログラムが利用するメモリ領域の種類の一つで、実行時に任意のタイミングで確保や解放が可能なものをヒープ領域というが、これをヒープと略す場合がある。データ構造のヒープ
親要素が複数の子要素を持つ、階層状に枝分かれしていくデータ構造を「木構造」(ツリー構造)というが、ヒープはその特殊な場合の一つである。「どの親要素も自分の子要素より常に大きいか等しい」(あるいは、常に小さいか等しい)という制約を満たすように構成されたものを指す。子要素間の関係に制約はない。
次の要素への参照を表すポインタ的なデータがなくても単純な配列などで実装でき、根要素(ルート要素)が常に最も大きく(あるいは小さく)なるという特徴がある。根要素を取り除いて残りの要素で木を再構築するという処理を繰り返して要素全体を整列(ソート)する手法を「ヒープソート」(heap sort)と呼び、最も高速なソートアルゴリズムの一つとして知られる。
ヒープ領域 (ヒープメモリ)
コンピュータプログラムが実行時に使用するメモリ領域の一つで、任意に確保や解放を繰り返すことができるものを「ヒープ領域」「ヒープエリア」(heap area)あるいは「ヒープメモリ」(heap memory)という。これを指して単にヒープと略すことも多く、データ構造のヒープと混同しないよう文脈に注意する必要がある。
(2024.9.6更新)
「ヒープ」の関連用語
他の用語辞典による「ヒープ」の解説 (外部サイト)
資格試験などの「ヒープ」の出題履歴
▼ 基本情報技術者試験
【平29修12 問17】 プログラムの実行時に利用される記憶領域にスタック領域とヒープ領域がある。それらの領域に関する記述のうち,適切なものはどれか。
【平29修1 問6】 親の節の値が子の節の値より小さいヒープがある。このヒープへの挿入は,要素を最後部に追加し,その要素が親よりも小さい間,親と子を交換することを繰り返せばよい。