ヒープ

heap.png

メモリ領域のヒープ

自由記憶領域と同義

データ構造のヒープ

Binary_heap_indexing.png
木構造の一つ。
ヒープは最小値(または最大値)を求めるのに適した木構造の一種
  • 「子要素は親要素より常に大きいか等しい(または常に小さいか等しい)」

という制約と持つ。
ヒープ(Heap)は、木構造の一つ。単に「ヒープ」という場合、二分木を使った二分ヒープを指すことが多いため、そちらを参照すること。
ヒープは最小値(または最大値)を求めるのに適した木構造の一種であり、
「子要素は親要素より常に大きいか等しい(または常に小さいか等しい)」という制約を持つ。
子要素が複数ある場合、子要素間の大小関係に制約はない。
優先度付きキューの実装としても使われる。
ダイクストラ法などのグラフ問題のアルゴリズムでも使われている。

ヒープの実装の仕方

用意すべき、一般的なヒープの関数は以下のものになる
Add…要素をヒープに挿入すること。要素はヒープの中で順番的に正しい位置に挿入する。
Pop….ヒープから要素を取り除く。一番上にある要素は、一番優先順位が高いか、一番低いかどっちかの要素である。
Top….今一番最上位にある要素を返す
Empty…ヒープが空かどうか調べること
C++にはSTLで優先度付きキューの型がある!PRIORITY_QUEUE<>である
#include <queue>
using namespace std;
void main(){
priority_queue<int> pq;
}
注意すべきなのは、C++のpriority_queue<>は 最も高い 要素を最初に返す、ということである。

参考リンク

TopCoderAlgorithm Tutorial

サポートサイト Wikidot.com