Hatena::Grouptopcoder

週刊 spaghetti_source

2012-10-06

Double-Ended Priority Queue

11:43

普通の優先度付きキュー(ヒープ)は

  • min
  • push
  • pop

の3つの操作が可能なデータ構造ですが,これに

  • max

も可能になったデータ構造が Double-Ended Priority Queue です.

競技プログラミング的には std::multiset(平衡二分木)で代替するのが良いケースがほとんどだと思いますが,平衡木と完全二分木を配列で実装したヒープはキャッシュ効率で大きく差がつくので,計算量がシビアな問題ではこれが原因でTLEになることも十分考えられます(厳密には比較回数の下限にも定数倍で差があるのですが,実測ではそんなものよりキャッシュ効率が支配的です).


DEPQの代表的な実装としては

  • dual heap (aka. twin heap)
  • min-max heap
  • interval heap

の3つがあると思っています.以下これらを説明します.ちなみに,自分が一番好きなのはInterval Heapです.考え方がシンプルだし,この中では実測でも一番高速です.なお,最近でもいくつか新しいDEPQ実装は提案されていますが,それらの論文中に実測比較が無く,自分でも実装していないので,詳しいパフォーマンスの事情は知りません.


Dual Heap

一番基本的なDEPQの実装です.最小ヒープと最大ヒープを用意して以下のようにします.

  • push(key): 両方のヒープに key を挿入
  • deleteMin: minHeap を pop, 対応する要素を maxHeap から remove
  • 他も同様

これは非常に単純なアイデアですが,字面の印象よりもずっと実装は大変です.試しに書いてみてください.

この手の同じデータ構造を並べてリンクでつなぐタイプの手法を Correspondence-based structure などといいますが,平衡二分木(Splay Tree)にすらパフォーマンス(比較回数と実行回数の両面)で勝てないと言われています(Chong-Sahni 2000).

メリットはどんなデータ構造でも「とりあえず使える」ということで,例えばMeldable Double-Ended Priority Queueを作りたいけどアルゴリズムを知らない,といったケースではこの技法で実装するのが一つの戦略になります.


Min-Max Heap

Min-Max Heap(Atkinson-Sack-Santoro-Strothotte(1986))は「偶数段目はMin-Heap,奇数段目はMax-Heap」であるヒープです.より正確には,以下の2条件を満たすものです:

  • 偶数段目のノードの値は,その子孫よりも小さい(Min Heap property)
  • 奇数段目のノードの値は,その子孫よりも大きい(Min Heap property)

push

要素を挿入する場合,普通と同じように完全二分木の末尾に挿入してheapUpするのですが,heapUpの前に一段回処理が必要です.自分が偶数段目(min level)にいる場合の処理は以下のようになります:

  • 自分の親(max level)と比較して,自分のほうが小さい場合は min level の中で heapUp する
  • 自分のほうが大きい場合は親と swap し,親から初めて max level の中で heapUp する

この処理でMin-Max Heap propertyが満たされることは,少し考えればわかります.

deleteMin

根と完全二分木の末尾を交換し,根をheapDownします.heapDownの処理は以下のようになります:

  • 自分の子・孫の中の最小要素を m としたとき,自分が m より小さければ交換.
  • 交換後の要素とその親でヒープ条件が崩れていたら修正.

deleteMax

根の子(深さ1のノード)のうち最大のものと末尾を交換し,heapDownします.


以下に実装例を示します.

// 51 lines
int log2(int n) { 
  int k = 0;
  for (; n; n >>= 1) ++k;
  return k-1;
}
const int MAXSIZE = 1000;
struct MinMaxHeap {
  int h[MAXSIZE];
  int size;
  void heapDown(int i, int b) {
    for (int m = i; ; i = m) {
      for (int c = i*2; c < min(size,i*2+2); ++c)
        if ((h[m] > h[c])^b) m = c;
      for (int g = i*4; g < min(size,i*4+4); ++g)
        if ((h[m] > h[g])^b) m = g;
      if (m == i) return;
      swap(h[m], h[i]);
      if (m - i*4 >= 0) 
        if ((h[m/2] < h[m])^b) swap(h[m/2], h[m]);
    }
  }
  void heapUp(int i, int b) {
    if (i > 1 && (h[i] > h[i/2])^b) { 
      swap(h[i], h[i/2]);
      b ^= 1; i /= 2;
    }
    for (int g; g = i >> 2; i = g) {
      if ((h[g] <= h[i])^b) break;
      swap(h[i], h[g]);
    }
  }
  void push(int x) { 
    h[size++] = x;
    heapUp(size-1,log2(size-1)%2); 
  }
  void deleteMin() { 
    h[1] = h[--size];
    heapDown(1, 0);
  }
  void deleteMax() {
    if (size == 2) return deleteMin();
    int m = 2;
    if (size >= 3 && h[3] > h[2]) m = 3;
    h[m] = h[--size];
    heapDown(m, 1);
  }
  int  findMin()   { return h[1]; }
  int  findMax()   { return size>3?max(h[2],h[3]):h[1+(size==3)]; }
  bool empty()     { return size == 1; }
  MinMaxHeap() : size(1) { }
};

Interval Heap

DEPQ実装で自分が一番好きなのがInterval Heap(Leeuwen-Wood, 1993)です.アイデアは非常に簡単で,以下のようなものです:

  • 完全二分木の各ノードは「区間」に対応する(2つずつ値を格納する,末尾の要素はシングルトン [x,x] ).
  • [l,r] が [L,R] の子のとき [l,r] ⊆ [L,R](Interval Heap Property)

最小値は根の左端点, 最大値は根の右端点を返せばOKです.

heapUp, heapDownも簡単で,変更のあった箇所と上下の包含関係をチェックして満たされていなければ満たされるように端点をスワップするのみです.

以下に実装例を示しますが,整理できていない段階で書いたものなので随分ヤヤコシくなっており,いずれ書き直す予定です.

// 54 lines
const int MAXSIZE = 10100100;
struct IntervalHeap {
  int h[MAXSIZE];
  int size, r;
  int &hof(int b, int i) { return h[b+2*i]; }
  void heapUp(int i, int b) {
    for (int p; p = i >> 1; i = p) {
      if (b ^ (hof(b,p) <= hof(b,i))) break;
      swap(hof(b,i), hof(b,p));
    }
  }
  void heapDown(int i, int b) {
    for (int c; (c = i << 1) < size+r; i = c) {
      if (c+1 < size+r && b ^ (hof(b,c) > hof(b,c+1))) ++c;
      if (b ^ (h[b+2*i] <= h[b+2*c])) break;
      swap(hof(b,i), hof(b,c));
      if (hof(0,c) > hof(1,c)) swap(hof(0,c), hof(1,c));
    }
  }
  void deleteMin() {
    if (r ^= 1) --size; else hof(1,size) = hof(0,size);
    hof(0,1) = hof(r,size);
    heapDown(1, 0);
  }
  void deleteMax() {
    if (size == r) return deleteMin();
    if (r ^= 1) --size; else hof(1,size) = hof(0,size);
    hof(1,1) = hof(r,size);
    heapDown(1, 1);
  }
  void push(int key) {
    hof(r,size) = key;
    if (r == 1) { // insert to large
      if (hof(0,size) > hof(1,size)) {
        swap(hof(0,size), hof(1,size));
        heapUp(size, 0); // min mode
      } else {
        heapUp(size, 1); // max mode
      }
    } else { // insert to large
      hof(1,size) = hof(0,size) = key;
      if (hof(0,size) < hof(0,size/2)) heapUp(size, 0);
      if (hof(1,size) > hof(1,size/2)) {
        heapUp(size, 1); 
        hof(0,size) = hof(1,size);
      }
    }
    if (!(r ^= 1)) ++size;
  }
  int findMin() { return hof(0,1); }
  int findMax() { return (size==r) ? hof(0,1) : hof(1,1); }
  bool empty() { return size+r == 1; }
  IntervalHeap() : size(1), r(0) { }
};

hogloidhogloid2012/10/06 20:28こんな感じのものは知られていないでしょうか、コメントお願いします:

普通(STLとか)のpriority_queue(以下PQ)を4つ用意する。

一つはminHeap ,もう一つはmaxHeap
両方のPQについて、同じ比較関数の削除用PQを用意する

minHeap、maxHeapは、top()やpop()を呼ばれる度に、
その削除用ヒープと本体でtop()の値が同じ間、削除用ヒープと本体両方でpop()するようにする

push:maxHeap,minHeapにそのままpush
min:minHeapのtop()を見る
max:maxHeapのtop()を見る

minpop:
maxHeapの削除用PQにminHeapのtop()を入れる
minHeapでpop()
maxpop:同様

1回の動作がO(logN)に収まらない場合もありますが、ならしO(logN)になるはずです

何か勘違いしてたらごめんなさい

spaghetti_sourcespaghetti_source2012/10/06 22:59なるほど,Functional DequeをPriority Queueに置き換えたバージョンですね.面白いです.Functional Dequeと同じ解析で,きちんと amortized O(log n)になっています.
名前は聞いたことがありませんが,関数型データ構造の分野では名前があるかもしれません.詳しい方が居ましたら補足お願いします.

折角なので,性能を実測してみました.n = 10100100 ランダム列の挿入削除,multiset以外グローバル配列で実装.g++ -O2.

4-PQ IntHeap multiset
5.03[sec] 3.77[sec] 17.73[sec]

4つ使う実装,優秀ですね.IntervalHeapと比べてこれしか遅れないなら上出来です.実装も相当軽いので,競技ではこれで正解かもしれません.
特にDual Heapとは性質が丸かぶりしているので,そっちを使うくらいならこっちを使え,は間違いなさそうです.