Programming Place Plus トップページ – 用語集
木構造のうち、親が子よりも大きいか等しい(あるいは小さいか等しい)というルールを常に満たすもののことです。
ヒープの根(一番上位の節)は、ヒープ内でもっとも大きい(あるいは小さい)ことが保証されるため、最大値や最小値を高速に取得することに適したデータ構造です。この特徴を応用して、根を取り除いては、ヒープを再構築するという手順を繰り返すと、ソートを実現することができます(ヒープソート)。また、優先度付きキューの実装に使われることもあります。
ヒープの解説が、アルゴリズムとデータ構造編【データ構造】第9章に、優先度付きキューの解説が第10章に、ヒープソートの解説が、アルゴリズムとデータ構造編【整列】第8章にあります。
ヒープにはさまざまなバリエーションがありますが、子の数が2個以内に限定され(つまり二分木であり)、配列だけで実現可能(節どうしを結ぶためのポインタや参照のような仕組みが不要)なヒープを二分ヒープと呼ぶことがあります。単にヒープといった場合、二分ヒープのことを指している場合が多いです。
メモリ領域としての「ヒープ(ヒープ領域)」と混同しないように注意してください。
Programming Place Plus のトップページへ