RSS
木構造のうち、親が子よりも大きいか等しい（あるいは小さいか等しい）というルールを常に満たすもののことです。
ヒープの根（一番上位の節）は、ヒープ内でもっとも大きい（あるいは小さい）ことが保証されるため、最大値や最小値を高速に取得することに適したデータ構造です。この特徴を応用して、根を取り除いては、ヒープを再構築するという手順を繰り返すと、ソートを実現することができます（ヒープソート）。また、優先度付きキューの実装に使われることもあります。
ヒープの解説が、アルゴリズムとデータ構造編【データ構造】第９章に、優先度付きキューの解説が第１０章に、ヒープソートの解説が、アルゴリズムとデータ構造編【整列】第８章にあります。
ヒープにはさまざまなバリエーションがありますが、子の数が２個以内に限定され（つまり二分木であり）、配列だけで実現可能（節どうしを結ぶためのポインタやリファレンスのような仕組みが不要）なヒープを二分ヒープと呼ぶことがあります。単にヒープといった場合、二分ヒープのことを指している場合が多いです。
メモリ領域としての「ヒープ（ヒープ領域）」と混同しないように注意してください。
Programming Place Plus のトップページへ
| はてなブックマーク に保存 | Pocket に保存 | Facebook でシェア |
| X で ポスト／フォロー | LINE で送る | noteで書く |
|
RSS
|
管理者情報 | プライバシーポリシー |