優先度付きキュー/Priority-Queue ｃ＋＋
ハトムギです。
今回はヒープと優先度付きキューについて書きます。
ヒープ
ヒープとは、データ構造の一種で、木構造（ツリー構造）のうち、親要素が子要素より常に大きい（あるいは小さい）という条件を満たすもの。また、コンピュータプログラムが利用するメモリ領域の種類の一つで、実行時に任意のタイミングで確保や解放が可能なものをヒープ領域というが、これをヒープと略す場合がある。
つまり、ややこしいですがデータ構造のヒープとメモリ領域のヒープの二種類があります。
優先度付きキューを実装するときは、データ構造のヒープの考え方を用います。
ヒープのための配列、ヒープの末尾を指すindexはグローバルに宣言しておいたら便利です。
int h = 0, a[max + 1] = { -1 };
優先度付きキュー
今回は、自由に数字を挿入、削除でき削除する際には最大の数字から削除するような優先度を持つキューを実装します。
挿入 void insert(int k)
引数の値をヒープの末尾に追加して、親より大きかったら親と入れ替えるのを繰り返す。
void insert(int k) {
h++;
a[h]= k;
int i = h;
while (i > 1 && a[i] > a[i / 2]) {
int swap = a[i];
a[i] = a[i / 2];
a[i / 2] = swap;
i /= 2;
}
}
最大ヒープ void maxheap(int i)
数列を、すべて子が親より小さくなるように並び替える関数です。
方針は、引数の左の子、右の子、が存在すれば、それらの中で一番大きい数を取り出し、その数が親になるように配列の要素を入れ替えます。
上記を木の葉に到達するか、引数が子よりも大きい位置にくるまで繰り返します。
void maxheap(int i) {
int l, r, lar;
l = 2 * i;
r = 2 * i + 1;
if (l <= h && a[l] > a[i])lar = l;
else lar = i;
if (r <= h && a[r] > a[lar])lar=r;
if (lar != i) {
int swap = a[lar];
a[lar] = a[i];
a[i] = swap;
maxheap(lar);
}
}
削除 void extract()
まず、ヒープの先頭の要素を出力します。
つぎに、ヒープの先頭に末尾の要素を格納してヒープ全体が最大ヒープになるようにします。
その後、要素が一つ減っているので、ｈから１引きます。
void extract() {
cout<<a[1]<<endl;
a[1] = a[h];
maxheap(1);
h--;
}
