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とは性質が丸かぶりしているので,そっちを使うくらいならこっちを使え,は間違いなさそうです.

STEWkaxySTEWkaxy2018/07/01 09:21There are different ways to fry tomatoes, but each of them will require the hostess to spend row hours in the kitchen, so this dish is usually better correct prepare on weekends or for special occasions. When tomatoes are roasted, they get a deep taste and are combined with seafood, antipasto and other roasted vegetables. Moreover, they are good suitable for application in the baking industry, in making bread or cake with custard.
<a href=http://stewedtomatoes.top/how-to-can-stewed-tomatoes-at-home>how to can stewed tomatoes</a>

AnnilepeAnnilepe2019/03/15 01:31In the first study of its kind, researchers at the center for brainhealth at the university of texas at dallas and the university of texas southwestern...
<a href=http://anoxia.info/what-is-a-co-occurring-disorder-anxiety-attack>anxiety disorder treatment</a>
4 Men share their honest experiences with anxiety and depression - men's health nanoxia deep silence 3 anthracite

AnnilepeAnnilepe2019/03/16 13:26The purpose of this study was to assess the effect of a soccer match on the cardiac autonomic control of heart rate (HR) in soccer referees. Sixteen...
<a href=http://anoxia.info/hypoxic-ischemic-encephalopathy-neurology-anoxic>anoxic brain damage pathophysiology</a>
Humplinks alcs wakes up, nlcs puts us all back to sleep. - halos heaven social anxiety assessment pdf

YolloWerYolloWer2019/03/18 04:52I really cannot say enough great things about Andrew Davis! He shot our wedding in September and did a phenomenal job! Not only was he extremely
<a href=http://gaselectricity.in/vital-capacity-new-health-guide-electricity>vital capacity</a>
Addicted to your smartphone arianna huffington and samsung have an app for that. - the washington post electricity and magnetism review sheet

BTCzokBTCzok2019/03/29 08:18El sitio web es utilizado por decenas de solteros en 24 paГ­ses de todo el mundo. Si decides actualizar al plan de penthouse, tendrГЎs acceso a su bГєsqueda
<a href=http://bitcoinsp.info/lercheherring2-colourlovers-donde-compro-bitcoins>dobrze zabezpieczone</a>
Casino en lГ­nea demuestra ser un enfoque maravilloso para saborear las estafas de bitcoin

ZukamoxZukamox2019/04/03 15:52Carbon Laser Facial Treatment is now available at Dr. Rachna's Skin Clinic. It is revolutionary treatment for Skin Rejuvenation
<a href=http://chemicalpeel.in/salon-deep-chemical-peel-before-and-after>deep chemical peel before and after</a>
Evaluation of processing tomatoes from two consecutive growing seasons: Quality attributes, peelability and yield Request PDF

TomredTomred2019/04/10 20:09No hay duda, Michael Fred Phelps II es uno de esos atletas que se mantendrГЎ en nuestras mentes y corazones, y en los de las generaciones venideras, por
<a href=http://escoliosislumbar.info/the-microsoft-platform-windows-virtual-desktop-rds>windows server</a>
Blue city health sure - home escoliosis dorsolumbar dextroconvexa

ZycMipsZycMips2019/04/14 14:57Los consumidores ahora estГЎn haciendo su propia investigaciГіn en un dispositivo mГіvil cuando estГЎn en la tienda a travГ©s de anuncios mГіviles y contenido
<a href=http://beneficiosdesegurosocial.cf/concepto-y-significado-de-la-seguridad-social>registro de llamadas</a>
Uc san diego postdocs mclc recurso centro seguridad social calificaciones Obtenga una nueva tarjeta de seguridad social, nГєmero de telГ©fono de seguridad social, cambio de nombre de seguridad social, oficina de administraciГіn de seguridad social, oficinas de seguridad social

BOLDutleBOLDutle2019/04/24 03:25Small Pea sized lump in armpit, what could it be? | Yahoo Answers
<a href=http://armpit.info/how-much-should-you-worry-about-painful-lump-under-armpit/>painful lump under armpit</a>

BernEncoxBernEncox2019/05/25 23:28Ankle soreness results from overuse and exhaustion of your feet: this usually means wearing a new pair of shoes or walking around more than usual. Ankle soreness is distinct from sharp pain, bruising, numbness, tingling, or burning...
http://magdalenabus.tk/page/why-does-my-tongue-feel-burnt/

PozzilibPozzilib2019/05/29 04:06Sanctuary Day Spas: I had a facial and massage - See 476 traveler reviews, 15 candid photos, and great deals for Concord, Canada, at TripAdvisor.
<a href=http://reflexology.nodes.top/art/east-holistic-reflexology/>East holistic reflexology</a>

NoniGapNoniGap2019/06/03 14:19Daniel Ott is the Cosmic Cowboy host of The Edge News Television Broadcast. Every week, along with parodies, investigative and educational journalism, youll hear exciting interviews on topics such as 9/11, Angels, Near Death Experiences, Planetary Anomal
<a href=http://anoxia.info/>anoxia symptoms</a>

CocoirowsCocoirows2019/06/06 05:54DONA International and our doulas have contributed to many articles including pieces by The New York Times, Essence magazine, The Washington Post, The Bump, Fit Pregnancy, and more! Let’s Connect! The DONA Doula Chronicles Blog
<a href=http://massage.nodes.top/art/prenatal-massage-tampa/>Prenatal massage tampa</a>

UhanawUhanaw2019/06/06 23:17Entrancing these considerations into account, we take it our treatment procedure is artistically justi?ed Routine daytime EEGs that comprise at least 20–30 min of slumber may capture ESES, but warning is advised in the occurrence of a negative daytime study in the background of cognitive, behavioral, or wording deterioration In this character the inexperience of others account is more
<a href=http://Haloperidol.nodes.top/haldol-decanoate-injection/1/>Haldol decanoate injection</a>

DENlariDENlari2019/06/11 01:58At Family & Cosmetic Dental Care, is a Johns Creek Dentist. We are proud to serve the areas of Johns Creek, Suwanee, Duluth, and all North Atlanta communities. Our comprehensive family dental practice specializes in building confident smiles through all stages of life, from children to seniors. Dr. Mitul Patel and his team focus on compassion and patient comfort, striving to put you at ease
<a href=http://denta.top/walk-in-dentist/1/>Walk in dentist</a>

BimsixBimsix2019/06/14 14:47But thanks to minimal branding (which consists primarily of the words Johnny Pag etched on the engine case), the Pro Street has a slick, poised
<a href=http://gaselectricity.in/witti-candi-wireless-charging-station-review-mac>phone charging</a>

TesnefTesnef2019/06/18 12:42Have to agree with wee man on this all of my dogs teeth have always been pearly white with no tartar ,I dont feed beef marrow bones but feed raw pork,lamb,chicken and pheasant bones #16 niamh123 , May 6, 2019
<a href=http://tartaronteeth.cf/art/tartar-buildup-on-bottom-front-teeth/>Tartar buildup on bottom front teeth</a>

DOLIkixDOLIkix2019/06/26 10:06At St. Louis Cosmetic Surgery, rapid recovery liposuction helps Belleville, Illinois, patients enhance their contours with reduced downtime. See patient photos.
<a href=http://chemicalpeel.in/acne-scars-before-and-after-chemical-peel-do-they-look>acne scars before and after chemical peel</a>

AcuraZekAcuraZek2019/06/26 20:39A recent report showed that there were nearly 23,000 tenant households in Washington earning at least $150,000 annually as of 2017—one of the highest totals of any major U.S. city.
<a href=http://acjointarthritis.cf/art/simple-arthritis/>Simple arthritis</a>

EGGtecyEGGtecy2019/06/27 16:33Huntersville dentist, Southlake Family and Cosmetic Dentistry is a local, trusted dental practice offering general and cosmetic dentistry, teeth whitening, implants, veneers & other dental care. Call today to make an appointment!
<a href=http://eggrolls.ml/art/egg-roll-nutrition/>Egg roll nutrition</a>

CepMumnCepMumn2019/07/17 13:30bitcoin, Crypto, cryptocurrency news, Industry, market Bitcoin Breaks Parabola With Big Downtrend, a BTC Correction Inbound? After managing to stay situated above $11,000 for a number of days, Bitcoin (BTC) has begun to slip.
<a href=https://bitcoinpor.top/para-ganhar-dinheiro-online-use-estas-dicas-da/>bitcoin forecast</a>

CraftbibCraftbib2019/09/14 07:33A custom Minecraft launcher for installing modpacks,дё‹иј‰Launcherзљ„жєђзўј
<a href=http://minecraft-game.ga/dailymed-inyeccion-de-gattex-teduglutida-polvo>minecraft heads</a>

MikoToorMikoToor2019/09/21 10:58We diagnose and treat all skin, hair, and nail conditions of adults and children including skin cancer screening, hair, nail & skin exams. Call Today.
<a href=http://psoriasisinchildren.ml/art/types-of-psoriasis-in-children1/>Types of psoriasis in children</a>

JonivedJonived2019/09/25 19:2313 Aug 2011 Proper installation is the key for your bathroom sink drain to function well in the long run. As the time goes by, the pipes and drains will loosen
<a href=http://sinkfaucets.cf/art/how-to-fix-a-leaky-bathroom-sink-faucet-double-handle2/>How to fix a leaky bathroom sink faucet double handle</a>

MugohigMugohig2019/10/05 18:37The tumor exhibits a geographically destructive growth pattern, but Gross Findings The gross appearance of malignant fibrous histiocytoma is highly variable
<a href=http://histiocytoma.cf/chemotherapy-and-benign-histiocytoma-human-radiation-therapy-in-the-management>histiocytoma</a>