- できるだけ毎週土曜日更新．次回更新は2月16日．
- ネタ切れ深刻なので記事リクエスト募集中．twitterないしはコメント欄まで．
- 貼っているコードはあんまり検証していないので，信頼性はアレです．アレ．
- twitter: @tmaehara フォローはお気軽に．
2012-10-06
Double-Ended Priority Queue
普通の優先度付きキュー（ヒープ）は
- min
- push
- pop
の３つの操作が可能なデータ構造ですが，これに
- max
も可能になったデータ構造が Double-Ended Priority Queue です．
競技プログラミング的には std::multiset（平衡二分木）で代替するのが良いケースがほとんどだと思いますが，平衡木と完全二分木を配列で実装したヒープはキャッシュ効率で大きく差がつくので，計算量がシビアな問題ではこれが原因でTLEになることも十分考えられます（厳密には比較回数の下限にも定数倍で差があるのですが，実測ではそんなものよりキャッシュ効率が支配的です）．
DEPQの代表的な実装としては
- dual heap (aka. twin heap)
- min-max heap
- interval heap
の３つがあると思っています．以下これらを説明します．ちなみに，自分が一番好きなのはInterval Heapです．考え方がシンプルだし，この中では実測でも一番高速です．なお，最近でもいくつか新しいDEPQ実装は提案されていますが，それらの論文中に実測比較が無く，自分でも実装していないので，詳しいパフォーマンスの事情は知りません．
Dual Heap
一番基本的なDEPQの実装です．最小ヒープと最大ヒープを用意して以下のようにします．
これは非常に単純なアイデアですが，字面の印象よりもずっと実装は大変です．試しに書いてみてください．
この手の同じデータ構造を並べてリンクでつなぐタイプの手法を 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」であるヒープです．より正確には，以下の２条件を満たすものです：
- 偶数段目のノードの値は，その子孫よりも小さい（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
根の子（深さ１のノード）のうち最大のものと末尾を交換し，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）です．アイデアは非常に簡単で，以下のようなものです：
- 完全二分木の各ノードは「区間」に対応する（２つずつ値を格納する，末尾の要素はシングルトン [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) { } };
- 64 https://topcoder-g-hatena-ne-jp.jag-icpc.org/
- 14 http://t.co/BITNri6X
- 6 http://t.co/rXGMbWEv
- 5 http://twipple.jp/?sticky=1
- 1 http://twipple.jp/
- 1 http://www.google.co.jp/reader/view/feed/http://d.hatena.ne.jp/ne210064/rss?at=f2em6XRg_Tb61QNCmHd-Ig
- 1 http://b.hatena.ne.jp/qnighy/
- 1 http://www.google.co.jp/ig
- 1 http://www.google.co.jp/reader/view/?hl=ja&tab=wy
- 1 http://www.google.co.jp/url?sa=t&rct=j&q=劣モジュラ不等式&source=web&cd=6&ved=0CEUQFjAF&url=https://topcoder-g-hatena-ne-jp.jag-icpc.org/spaghetti_source/20120915/1347668163&ei=fEpwUMOrHIHJmQWkioCwBg&usg=AFQjCNGYlG1Rrm1ww5vu6cZNkbfYtVtZcg&cad=rja
普通（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:同様
１回の動作がO(logN)に収まらない場合もありますが、ならしO(logN)になるはずです
何か勘違いしてたらごめんなさい
名前は聞いたことがありませんが，関数型データ構造の分野では名前があるかもしれません．詳しい方が居ましたら補足お願いします．
折角なので，性能を実測してみました．n = 10100100 ランダム列の挿入削除，multiset以外グローバル配列で実装．g++ -O2．
4-PQ IntHeap multiset
5.03[sec] 3.77[sec] 17.73[sec]
４つ使う実装，優秀ですね．IntervalHeapと比べてこれしか遅れないなら上出来です．実装も相当軽いので，競技ではこれで正解かもしれません．
特にDual Heapとは性質が丸かぶりしているので，そっちを使うくらいならこっちを使え，は間違いなさそうです．
<a href=http://stewedtomatoes.top/how-to-can-stewed-tomatoes-at-home>how to can stewed tomatoes</a>
<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
<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
<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
<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
<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
<a href=http://escoliosislumbar.info/the-microsoft-platform-windows-virtual-desktop-rds>windows server</a>
Blue city health sure - home escoliosis dorsolumbar dextroconvexa
<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
<a href=http://armpit.info/how-much-should-you-worry-about-painful-lump-under-armpit/>painful lump under armpit</a>
http://magdalenabus.tk/page/why-does-my-tongue-feel-burnt/
<a href=http://reflexology.nodes.top/art/east-holistic-reflexology/>East holistic reflexology</a>
<a href=http://anoxia.info/>anoxia symptoms</a>
<a href=http://massage.nodes.top/art/prenatal-massage-tampa/>Prenatal massage tampa</a>
<a href=http://Haloperidol.nodes.top/haldol-decanoate-injection/1/>Haldol decanoate injection</a>
<a href=http://denta.top/walk-in-dentist/1/>Walk in dentist</a>
<a href=http://gaselectricity.in/witti-candi-wireless-charging-station-review-mac>phone charging</a>
<a href=http://tartaronteeth.cf/art/tartar-buildup-on-bottom-front-teeth/>Tartar buildup on bottom front teeth</a>
<a href=http://chemicalpeel.in/acne-scars-before-and-after-chemical-peel-do-they-look>acne scars before and after chemical peel</a>
<a href=http://acjointarthritis.cf/art/simple-arthritis/>Simple arthritis</a>
<a href=http://eggrolls.ml/art/egg-roll-nutrition/>Egg roll nutrition</a>
<a href=https://bitcoinpor.top/para-ganhar-dinheiro-online-use-estas-dicas-da/>bitcoin forecast</a>
<a href=http://minecraft-game.ga/dailymed-inyeccion-de-gattex-teduglutida-polvo>minecraft heads</a>
<a href=http://psoriasisinchildren.ml/art/types-of-psoriasis-in-children1/>Types of psoriasis in children</a>
<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>
<a href=http://histiocytoma.cf/chemotherapy-and-benign-histiocytoma-human-radiation-therapy-in-the-management>histiocytoma</a>
<a href=http://dentures.denta.top/sitemap.php>Sitemap</a>
<a href=http://howtogetridofacnescars.ga/female-probiotics-how-to-get-rid-of-acne-and-acne-scars-naturally-the-10-best>how to get rid of acne and acne scars naturally</a>
<a href=http://howtosavemoneyfast.cf/6-simple-tips-for-buying-certified-coins-how-to-make-and-save-money-fast-u-s>how to save money fast</a>
<a href=http://howtogetridofantsinhouse.ga/bbc-how-to-get-rid-of-small-ants-in-your-house-future-can-decluttering-your>how to get rid of ants in house</a>
<a href=http://makemoneyonlinemoney.info/c34e-ways-to-make-small-money-edgeless-in-ceiling-speaker-rsl-speakers>ways to make money</a>
<a href=http://itchypatchesonskin.ml/deep-vein-thrombosis-patches-of-itchy-bumps-on-skin-dvt-blood-clot-in-leg>patches of itchy bumps on skin</a>
<a href=http://nauseainthemorning.ml/atlanta-braves-what-causes-nausea-in-the-morning-besides-pregnancy-minor-league>nausea in the morning</a>
<a href=http://yeastinfectiontreatment.info/hhs-declares-public-health-emergencies-ahead-of-hurricane-is-a-yeast-infection>yeast infection</a>