先頭へ戻る

ヒープ | Programming Place Plus 用語集

Programming Place Plus トップページ用語集

先頭へ戻る

名称

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

解説

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

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

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

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


参考リンク

更新履歴


用語集のトップページへ

Programming Place Plus のトップページへ



はてなブックマーク に保存 Pocket に保存 Facebook でシェア
Twitter でツイート Twitter をフォロー LINE で送る
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー