ヒープ | Programming Place Plus 用語集

トップページ用語集

名称

このページでは、データ構造としての「ヒープ」を取り上げています。このほか、メモリ領域としての「ヒープ」があります。

解説

木構造のうち、親が子よりも大きいか等しい(あるいは小さいか等しい)というルールを常に満たすもののことです。

ヒープの根(一番上位の)は、ヒープ内でもっとも大きい(あるいは小さい)ことが保証されるため、最大値や最小値を高速に取得することに適したデータ構造です。この特徴を応用して、根を取り除いては、ヒープを再構築するという手順を繰り返すと、ソートを実現することができます(ヒープソート)。また、優先度付きキューの実装に使われることもあります。

ヒープの解説が、アルゴリズムとデータ構造編【データ構造】第9章に、優先度付きキューの解説が第10章に、ヒープソートの解説が、アルゴリズムとデータ構造編【整列】第8章にあります。

ヒープにはさまざまなバリエーションがありますが、子の数が2個以内に限定され(つまり二分木であり)、配列だけで実現可能(節どうしを結ぶためのポインタリファレンスのような仕組みが不要)なヒープを二分ヒープと呼ぶことがあります。単にヒープといった場合、二分ヒープのことを指している場合が多いです。


メモリ領域としての「ヒープ(ヒープ領域)」と混同しないように注意してください。


参考リンク

更新履歴


用語集のトップページへ

Programming Place Plus のトップページへ



はてなブックマーク に保存 Pocket に保存 Facebook でシェア
X で ポストフォロー LINE で送る noteで書く
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー
先頭へ戻る