ヒープ 【heap】

概要

ヒープ（heap）とは、データ構造の一種で、木構造(ツリー構造)のうち、親要素が子要素より常に大きい(あるいは小さい)という条件を満たすもの。また、コンピュータプログラムが利用するメモリ領域の種類の一つで、実行時に任意のタイミングで確保や解放が可能なものをヒープ領域というが、これをヒープと略す場合がある。

データ構造のヒープ

親要素が複数の子要素を持つ、階層状に枝分かれしていくデータ構造を「木構造」（ツリー構造）というが、ヒープはその特殊な場合の一つである。「どの親要素も自分の子要素より常に大きいか等しい」（あるいは、常に小さいか等しい）という制約を満たすように構成されたものを指す。子要素間の関係に制約はない。

次の要素への参照を表すポインタ的なデータがなくても単純な配列などで実装でき、根要素（ルート要素）が常に最も大きく（あるいは小さく）なるという特徴がある。根要素を取り除いて残りの要素で木を再構築するという処理を繰り返して要素全体を整列（ソート）する手法を「ヒープソート」（heap sort）と呼び、最も高速なソートアルゴリズムの一つとして知られる。

ヒープ領域 (ヒープメモリ)

コンピュータプログラムが実行時に使用するメモリ領域の一つで、任意に確保や解放を繰り返すことができるものを「ヒープ領域」「ヒープエリア」（heap area）あるいは「ヒープメモリ」（heap memory）という。これを指して単にヒープと略すことも多く、データ構造のヒープと混同しないよう文脈に注意する必要がある。

この記事の著者 ： (株)インセプト IT用語辞典 e-Words 編集部
1997年8月より「IT用語辞典 e-Words」を執筆・編集しています。累計公開記事数は1万ページ以上、累計サイト訪問者数は1億人以上です。学術論文や官公庁の資料などへも多数の記事が引用・参照されています。