両端優先度付きキューのInterval-Heap実装

ヒープ / Double-Ended Priority Queue

優先度付きキュー、使い勝手が良くヒープ実装も簡単でデータ構造の入門書に書いて有ることも多いと思う。実装したのは勉強しだした最初の頃の1回だけな気がするので復習のために実装する。
G++のstd::priority_queueはmaxを取ることのできるヒープ構造であるが、今回の実装ではmax/minのどちらでもget/popのできる「両端優先度付きキュー」 wikipedia:en:Double-ended_priority_queue を実装したい。
実装はinterval heap が実装量・実行時間・メモリすべて良さそう。
stdにあるヒープは

• make_heap(first, last): 引数のvectorなどをヒープ構造に成るように並び替える。特に先頭を優先度最大の要素にする。
• push_heap(first, last): [first, last-1) がヒープのときに、末端の要素をpushして[first, last)をヒープにする。
• pop_heap(first, last): ヒープから優先度最大（先頭）の要素をpopして残りの要素でヒープにする。

これらをラップするとstd::priority_queueになるが、近いインターフェースで実装したい。両端キューにするのでget/popはget_min, get_max, pop_min, pop_max を実装することにする。

計算量

make_heap	O(n)
push	O(log n) amortize
pop_min, pop_max	O(log n)
get_min, get_max	O(1)
メモリ	2 * n * sizeof(T) + c

stdではget_minとpop_minができないのでそこが最大の違い。vectorで実装するためメモリ使用量は最大2倍としているが、データをコピーして複数持つようなことはしない。また、vectorのためpush_heapは償却計算量である。

面白いのはmake_heap、適当なデータ列が与えられたときにヒープを作るのはO(n)であるというところ。1要素づつpushしていくとO(n log n)であるところをmax-heap構造でもinterval-heap構造でもうまく実装するとO(n)に改良できる。

Interval-Heap

ヒープは木構造であるが、配列上でインデックスを操作するだけで親や子に移動できる。Interval-Heapは厳密には木構造ではない気もするがほぼ同じ。
interval-heapでは配列の偶数インデックス上にmax-heapを作り、奇数インデックス上にmin-heapを作る。

画像は9要素で作られたinterval-heapの例。矢印の始点が終点より大きい優先度を持つように適切なswapを繰り返す。
この構造はDAGでindex 0から1までの距離がO(log n)、更に次数も少なくpushやpopのときにO(log n)でヒープの条件を満たすように値を置き換えることができる。

コード

template<class T> struct PriorityQueue {
    vector<T> d;

    PriorityQueue() {}

    PriorityQueue(const vector<T> &d_) : d(d_) {
	make_heap();
    }

    template<class Iter> PriorityQueue(Iter first, Iter last) : d(first, last) {
	make_heap();
    }

    void push(const T &x) {
	int k = d.size();
	d.push_back(x);
	up(k);
    }

    void pop_min() {
	if (d.size() < 3u) {
	    d.pop_back(); 
	} else {
	    swap(d[1], d.back()); d.pop_back();
	    int k = down(1);
	    up(k);
	}
    }

    void pop_max() {
	if (d.size() < 2u) { 
	    d.pop_back();
	} else {
	    swap(d[0], d.back()); d.pop_back();
	    int k = down(0);
	    up(k);
	}
    }

    const T& get_min() const {
	return d.size() < 2u ? d[0] : d[1];
    }

    const T& get_max() const {
	return d[0];
    }

    int size() const { return d.size(); }

    bool empty() const { return d.empty(); }

    void make_heap() {
	for (int i=d.size(); i--; ) {
	    if (i & 1 && d[i-1] < d[i]) swap(d[i-1], d[i]);
	    int k = down(i);
	    up(k, i);
	}
    }

    inline int parent(int k) const {
	return ((k>>1)-1)&~1;
    }

    int down(int k) {
	int n = d.size();
	if (k & 1) { // min heap
	    while (2*k+1 < n) {
		int c = 2*k+3;
		if (n <= c || d[c-2] < d[c]) c -= 2;
		if (c < n && d[c] < d[k]) { swap(d[k], d[c]); k = c; }
		else break;
	    }
	} else { // max heap
	    while (2*k+2 < n) {
		int c = 2*k+4;
		if (n <= c || d[c] < d[c-2]) c -= 2;
		if (c < n && d[k] < d[c]) { swap(d[k], d[c]); k = c; }
		else break;
	    }
	}
	return k;
    }

    int up(int k, int root=1) {
	if ((k|1) < (int)d.size() && d[k&~1] < d[k|1]) {
	    swap(d[k&~1], d[k|1]);
	    k ^= 1;
	}

	int p;
	while (root < k && d[p=parent(k)] < d[k]) { // max heap
	    swap(d[p], d[k]);
	    k = p;
	}
	while (root < k && d[k] < d[p=parent(k)|1]) { // min heap
	    swap(d[p], d[k]);
	    k = p;
	}
	return k;
    }
};

終わりに

std::multisetでは同様の操作ができるがそれよりは機能を特化している分、効率のよいデータ構造である。復習のために書いたが両端優先度付きキューは使いどころがなさそう。今まで必要になったことがないので経験上これからも必要にならない。wikipedia先生によれば大量のデータをソートするときにpivotをメモリいっぱい取りキューに突っ込むという応用があるらし。