順位キューとヒープ 基本アルゴリズム

順位キュー

キューを使用する多くの場合、必ずしも完全に整列している必要もなく、すべてのレコードが同時に必要になることもない。また、レコードの中で最大要素を処理し次にもっと多くのレコードを集めてその中で現時点での最大要素を処理することが多い。こういう状況では、新しい要素を挿入し最大値を削除する操作のできるデータ構造が適切。このようなデータ構造を順位キューという。

プログラム9.1　順位キューのインターフェース

void PQinit(int);
int PQempty();
void PQinsert(Item);
Item PQdelmax();

プログラム9.2　配列による順位キューの実現

#include <stdlib.h>
#include "Item.h"

#define key(A) (A)
#define less(A, B) (key(A) < key(B))
#define exch(A, B) {Item t = A; A = B; B = t;}
#define compexch(A, B) if (less(B, A)) exch(A, B)
#define maxN 100

static Item *pq;
static int N;
void PQinit(int maxN) {
    pq = malloc(maxN*sizeof(Item));
    N = 0;
}

int PQempty() {
    return N == 0;
}

void PQinsert(Item v) {
    pq[N++] = v;
}

Item PQdelmax() {
    int j, max = 0;
    for (j = 1; j < N; j++)
        if (less(pq[max], pq[j]))
            max = j;
    exch(pq[max], pq[N-1]);
    return pq[--N];
}

ヒープの定義

各節点がその子のどれよりもキーが大きいか等しいということが成り立つ時、木はヒープ順に並んでいるという。ヒープ順に並ぶ木の各節点のキーはその節点の親のキーより小さいか等しい。

性質

ヒープ順に並ぶ木においてどの節点よりも根の節点より大きいキーをもつことはない。

ヒープの定義2

ヒープとは配列で表現された節点の集合でありそのキーが完全二分木の中にヒープ順に並んでいるもの

完全二分木の節点の個数をNとすると、任意の道の上にある節点の個数はたかだか約logNである。一番下に節点が約N/２個、一番下の節点を子にもつ節点が約N/4個、その上の節点が約N/8個になる。以下同様。どの世代も下の世代の約半分の節点数をもつので世代の個数は約logNである

ヒープのアルゴリズム

ヒープによる順位キューのアルゴリズムは最初にヒープ条件を壊すかもしれない簡単な修正を加え次にヒープをたどりながらヒープ条件を満たすように修復する。この過程はヒープ化またはヒープの修復という。

プログラム9.3　ボトムアップのヒープ化
一番下の節点からはじめてその親と比較し親より大きければその節点を親と交換する（kの親はk/2の位置にある）。この処理をa[k/2] < a[k]が成り立つ限り続ける。また、根に着くと終了する。

void fixUp(Item a[], int k) {
    while (k > 1 && less(a[k/2], a[k])) {
        exch(a[k], a[k/2]);
        k = k/2;
    }
}

プログラム9.4　トップダウンのヒープ化
位置kの節点と二つの子の節点の大きい方と比較して子の方が大きいと二つの節点を交換しながらヒープを降りていく。位置kの節点がどちらの子よりも小さくないか底に着くと終了する

void fixDown(Item a[], int k, int N) {
    int j;
    while (2*k <= N) {
        j = 2*k;
        if (j < N && less(a[j], a[j+1])) j++;
        if (!less(a[k], a[j])) break;
        exch(a[k], a[j]);
        k = j;
    }
}

操作insertは新しい要素を末尾に追加してヒープ条件を修復するためにその要素をヒープの中で上方に移動することになる。一方操作delete_the_maximumは一番上の最大値を取り除き、ヒープの末尾の要素を一番上におきヒープ条件を修復するためにその要素をヒープの中で下方に移動することになる。

性質

順位キューの抽象データ型に対する操作insertとdelete_the_maximumはヒープ順の木を用いて実現できる。ここで項目N個の順位キューに対してinsertはたかだかlogNの比較回数で実行できdelete_the_maximumはたかだか2logNの比較回数で実行できる。

両方の操作はヒープの根と底の間の道に沿って進む。大きさNのヒープはどの道よりもlogNより多くの要素を含まない。delete_the_maximumでは節点一つ当たり2回比較する（子のうち大きいキーを持つものを見つけるのに一回、大きい方の子を昇進させるかどうかを決めるのに比較一回を行う。

プログラム9.5　ヒープに基づく順位キュー

#include <stdlib.h>
#include "Item.h"
static Item *pq;
static int N;

void PQinit(int maxN) {
    pq = malloc((maxN + 1)*sizeof(Item));
    N = 0;
}

int PQempty() {
    return N == 0;
}

void PQinsert(Item v) {
    pq[++N] = v;
    fixUp(pq, N);
}

Item PQdelmax() {
    exch(pq[1], pq[N]);
    fixDown(pq, 1, N-1);
    return pq[N--];
}

性質

順位キューの抽象データ型に対する操作change_priority、delete、replace_the_maximumはヒープ順の木を使って実現できる。項目N個の順位キューに対してこれらの操作は高々2logNの比較回数で実現できる。

プログラム9.6　順位キューによる整列

void PQsort(Item a[], int l, int r) {
    int k;
    PQinit(r-l+1);
    for (k = l; k <= r; k++)
        PQinsert(a[k]);
    for (k = r; k >= l; k--)
        a[k] = PQdelmax();
}