読者です 読者をやめる 読者になる 読者になる

両端優先度付きキューの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を作る。
f:id:natsugiri:20161010032645p:plain
画像は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をメモリいっぱい取りキューに突っ込むという応用があるらし。

ACM-ICPC 2016 Asia Tsukuba Regional 国内予選 参加しなかった記

寝食も忘れて、なけなしの社交性も忘れて、プログラミングコンテストに励んでいた1年前の自分、今ではすっかり更生しプログラミングコンテストに出ることも減ってしまった。しかしICPCは解かずには居られない。
※ 私は参加者・選手では無い

リンク

続きを読む

ACM-ICPC 2016 Asia Tsukuba Regional 国内予選, H 解答

H: プレゼント交換会

問題

無向グラフがある。全ての辺に向きをつけなさい。そのとき、すべての頂点の入次数の最大値と最小値の差が最小に成るようにし、その時の最大値・最小値を出力せよ。
複数ある場合は最小値を最大化せよ。

続きを読む

ACM-ICPC 2016 Asia Tsukuba Regional 国内予選, G 解答

G: ワープ航法

問題

平面上に2つのワープ場を設置したい。ワープ場にたどり着いた航空便は平面の任意の位置に瞬時に移動する事ができる。今、2次元平面上に n箇所の街がある。m本の航空便があり、航空便はある街a_iから他の街b_iへ、速さv_iで直線距離で最短のルートを選択し、移動するものである。
任意のワープポイントの置き方に対し、「各便について最短時間の2乗」の総和を最小化せよ。

続きを読む

ACM-ICPC 2016 Asia Tsukuba Regional 国内予選, F 解答

F: 文字解読

問題

グリッドの2値画像が与えられる。この画像は「文字」として認識することができる。

  1. 白マスは4方向に連結する
  2. 黒マスは8方向に連結する
  3. 画像の外側は無限に白マスとし、背景と呼ぶ

また、白マスや黒マスの連結成分について包含の条件がある(省略)。
包含関係を連結成分同士の二項関係とすると、その二項関係を「文字」の定義とする。

2つの画像が与えられたとき、その画像が同じ「文字」かどうか判定せよ。
同じ「文字」であるとは、二項関係が保存される連結成分の全単射が存在することである。

続きを読む

ACM-ICPC 2016 Asia Tsukuba Regional 国内予選, E 解答

E: 3D プリント

問題

3次元空間に1辺長さsの立方体の設計図が n個ある。全ての立方体は3つの軸に平行で、頂点は整数座標。
ある2つの立方体が共通部分を持つとき連結しているといい、複数の立方体が次々に連結していれば大きな一つの立体になる。
n個の設計図からk個選んで立体を置いたとき、一つの立体に成るようにしなければならない。
このとき、その大きい立体の表面積の最小値を出力せよ。
入力のn個の立方体は次の条件を満たしている。

  1. 各立方体は0個・1個・2個の立方体と連結することはあるが、3個以上の立方体と連結することはない
  2. ある立方体が2個の立方体と連結するとき、その2つは連結していない
  3. どの2つの立方体も頂点・辺・面で接することはない。真に離れているか、真に共通部分を持つかのどちらかである
続きを読む

ACM-ICPC 2016 Asia Tsukuba Regional 国内予選, D 解答

D: ダルマ落とし

問題

長さnの数列aが与えられる。次の操作を好きなだけ繰り返す。

  • 数列の任意の隣り合う2数を一つ選び、その差の絶対値が1以下ならばその2数を数列から取り除き、数列は詰めて長さが2短くする

最大で幾つ取り除くことができるか。

続きを読む