ブロダルキュー
ブロダルキュー
タイプヒープ/優先キュー
発明された1996
発明者ゲルト・ストルティング・ブロダル
ビッグO記法による時間計算量
手術平均最悪の場合
空間複雑性

コンピュータサイエンスにおいて、ブロダルキューは、挿入、最小値検索、メルド（2つのキューのマージ）、キー減少、および最小値削除と一般的な削除において、最悪ケースの時間制限が非常に低いヒープ/優先度キュー構造です。ブロダルキューは、運用コストの償却に頼ることなくこれらの制限を達成した最初のヒープ変種です。ブロダルキューは、発明者であるゲルト・ストルティング・ブロダルにちなんで名付けられました。[ 1 ]お（1）{\displaystyle O(1)}お（loグラム（n））{\displaystyle O(\mathrm {log} (n))}

他の優先キュー構造よりも漸近的な境界値を持っているものの、ブロダル自身の言葉によれば、「非常に複雑」であり、「実際には適用できない」とのことです。[ 1 ]ブロダルとオカサキは、ブロダルキューの永続的（純粋に機能的な）バージョンについて説明しています。 [ 2 ]

意味

Brodalキューは、2つのツリー と5つのガイドのセットです。ガイドデータ構造の定義については、次のセクションを参照してください。どちらのツリーでも、各ノードにはランクがあります。このランクは後の操作に役立ち、直感的には、そのノードをルートとするサブツリーのサイズの対数に対応します。ランクのノードの子の数に注目してください。また、ツリーのルートにはを、ツリーのルートにはを使用します。特定の時点で、ノードをルートとするすべてのサブツリーは、次の5つの不変条件（以降、不変条件と呼びます）を満たす必要があります。 T1{\displaystyle T_{1}}T2{\displaystyle T_{2}}arity私（×）{\displaystyle {\text{arity}}_{i}(x)}×{\displaystyle x}私{\displaystyle i}t1{\displaystyle t_{1}}T1{\displaystyle T_{1}}t2{\displaystyle t_{2}}T2{\displaystyle T_{2}}ランク{\displaystyle {\text{RANK}}}

  • リーフランク{\displaystyle {\text{LEAF-RANK}}} :が葉である場合、×{\displaystyle x}ランク（×）＝0{\displaystyle {\text{rank}}(x)=0}
  • 親ランク{\displaystyle {\text{親ランク}}} : 、ランク（×）<ランク（親（×））{\displaystyle {\text{rank}}(x)<{\text{rank}}({\text{parent}}(x))}
  • ネクストランクアリティ{\displaystyle {\text{NEXT-RANK-ARITY}}} :ならば、ランク（×）>0{\displaystyle {\text{rank}}(x)>0}arityランク（×）−1（×）⩾2{\displaystyle {\text{arity}}_{{\text{rank}}(x)-1}(x)\geqslant 2}
  • ARITY-BOUND{\displaystyle {\text{ARITY-BOUND}}}:私たちは、arity私（×）∈{0、2、3、…、7}{\displaystyle {\text{arity}}_{i}(x)\in \{0,2,3,\dots ,7\}}arity私（×）≠1{\displaystyle {\text{arity}}_{i}(x)\neq 1}
  • ルートランク{\displaystyle {\text{ルートランク}}} ：または。T2＝∅{\displaystyle T_{2}=\emptyset }ランク（t1）⩽ランク（t2）{\displaystyle {\text{rank}}(t_{1})\leqslant {\text{rank}}(t_{2})}

ここで、 は、あるノードを根とする部分木のサイズが、そのノードのランクの指数関数以上であることを保証します。さらに、 は与えられたノードの各ランクの子の数を制限します。これは、すべてのノードが のランクと次数を持つことを意味します。 ネクストランクアリティ{\displaystyle {\text{NEXT-RANK-ARITY}}}ARITY-BOUND{\displaystyle {\text{ARITY-BOUND}}}お（ログ⁡n）{\displaystyle O(\log n)}

Brodal キューでは、すべてのノードが親よりも大きな値を持つわけではありません。この条件を回避するノードは違反ノードと呼ばれます。ただし、違反ノードの数を比較的少なくする必要があります。違反ノードを追跡するために、各ノードに対して、よりも大きいノードの2 つのセットとを作成します。直感的に、は よりも大きく、ランクが大きいノード ( の場合は となる)であり、はランクが小さいノード ( ) です。これらのセットは、双方向リンク リストを使用して実装されており、順序 を持ちます。特に、 に追加された違反ノードはすべてリストの先頭に追加され、 に追加された違反ノードはすべて同じランクのノードの隣に挿入されます。 はランクの内のノードの数を表すものとします。リストとリストは、次の 5 つの不変条件を満たします (不変条件を と呼びます)。 V（×）{\displaystyle V(x)}W（×）{\displaystyle W(x)}×{\displaystyle x}V（×）{\displaystyle V(x)}×{\displaystyle x}y∈V（×）{\displaystyle y\in V(x)}ランク（y）⩾ランク（t1）{\displaystyle {\text{rank}}(y)\geqslant {\text{rank}}(t_{1})}W（×）{\displaystyle W(x)}ランク（y）<ランク（t1）{\displaystyle {\text{rank}}(y)<{\text{rank}}(t_{1})}V（×）{\displaystyle V(x)}W（×）{\displaystyle W(x)}わ私（×）{\displaystyle w_{i}(x)}W（×）{\displaystyle W(x)}私{\displaystyle i}V（×）{\displaystyle V(x)}W（×）{\displaystyle W(x)}セット{\displaystyle {\text{SETS}}}

  • 最小ノード{\displaystyle {\text{最小ノード}}} :t1＝分（T1∪T2）{\displaystyle t_{1}=\min(T_{1}\cup T_{2})}
  • 違反条件{\displaystyle {\text{条件違反}}} : もしそうならy∈V（×）∪W（×）{\displaystyle y\in V(x)\cup W(x)}y⩾×{\displaystyle y\geqslant x}
  • 親を侵害する{\displaystyle {\text{親権を侵害する}}}:すると、次のようなノードが存在する。y<親（y）{\displaystyle y<{\text{parent}}(y)}×≠y{\displaystyle x\neq y}y∈V（×）∪W（×）{\displaystyle y\in V(x)\cup W(x)}
  • Wランクバウンド{\displaystyle {\text{Wランク境界}}}:わ私（×）⩽6{\displaystyle w_{i}(x)\leqslant 6}
  • Vランクバウンド{\displaystyle {\text{Vランク境界}}}: と表記すると、次の関係が成り立ちます。特定の定数 に対して。V（×）＝（v|V（×）|、…、v2、v1）{\displaystyle V(x)=(v_{|V(x)|},\dots ,v_{2},v_{1})}ランク（v私）⩾⌊私−1α⌋{\displaystyle {\text{rank}}(v_{i})\geqslant \left\lfloor {\frac {i-1}{\alpha }}\right\rfloor }α{\displaystyle \alpha}

すべてのノードはおよびのランクを持っているため、すべてのおよび のサイズは です。 お（ログ⁡n）{\displaystyle O(\log n)}Wランクバウンド{\displaystyle {\text{Wランク境界}}}Vランクバウンド{\displaystyle {\text{Vランク境界}}}V（×）{\displaystyle V(x)}W（×）{\displaystyle W(x)}お（ログ⁡n）{\displaystyle O(\log n)}

また、木の根と の不変量もいくつかあります。および（不変量と呼ばれる） T1{\displaystyle T_{1}}T2{\displaystyle T_{2}}t1{\displaystyle t_{1}}t2{\displaystyle t_{2}}ルーツ{\displaystyle {\text{ルーツ}}}

  • ルートアリティ{\displaystyle {\text{ルートアリティ}}} : 、t私∈{2、3、…、7} のために 私∈{0、1、…、ランク（t私）−1}{\displaystyle t_{i}\in \{2,3,\dots ,7\}{\text{ }}i\in \{0,1,\dots ,{\text{rank}}(t_{i})-1\}}
  • Vサイズバウンド{\displaystyle {\text{V-SIZE-BOUND}}}: 、|V（×）|⩽α ランク（t1）{\displaystyle |V(x)|\leqslant \alpha {\text{rank}}(t_{1})}
  • W-要素-ランク{\displaystyle {\text{W-ELEMENTS-RANK}}}: ならば、。y∈W（t1）{\displaystyle y\in W(t_{1})}ランク（y）<ランク（t1）{\displaystyle {\text{rank}}(y)<{\text{rank}}(t_{1})}

不変式は本質的に、 の階数を1つ増やしても、不変式に違反することなく、最大で新たな「大きな」違反（ここで「大きな」とは高い階数を持つことを意味する）が生じることを示しています。一方、不変式は におけるすべての違反が「小さい」ことを示しており、この不変式は の定義に照らして真です。不変式と の維持は容易ではありません。これらを維持するために、次のセクションで定義されるガイドを用いて実装できる 操作を使用します。 操作を呼び出すたびに、基本的に次の処理が実行されます。 Vサイズバウンド{\displaystyle {\text{V-SIZE-BOUND}}}t1{\displaystyle t_{1}}α{\displaystyle \alpha}Vランクバウンド{\displaystyle {\text{Vランク境界}}}W-要素-ランク{\displaystyle {\text{W-ELEMENTS-RANK}}}W（×）{\displaystyle W(x)}W{\displaystyle W}Wランクバウンド{\displaystyle {\text{Wランク境界}}}ルートアリティ{\displaystyle {\text{ルートアリティ}}}減少キー{\displaystyle {\text{DecreaseKey}}}減少キー{\displaystyle {\text{DecreaseKey}}}

  1. 違反のランクに応じて、新しい違反をまたはに追加します。V（t1）{\displaystyle V(t_{1})}W（t1）{\displaystyle W(t_{1})}
  2. サイズが大きくなりすぎないようにするために、次の 2 種類の変換を段階的に実行します。 V（t1）{\displaystyle V(t_{1})}W（t1）{\displaystyle W(t_{1})}
    1. の息子を移動させてランクを上げるt2{\displaystyle t_{2}}t1{\displaystyle t_{1}}t1{\displaystyle t_{1}}
    2. ランク違反2件をランク違反1件に置き換えることで違反件数を削減W（t1）{\displaystyle W(t_{1})}け{\displaystyle k}け+1{\displaystyle k+1}

ガイドデータ構造

この定義はブロダルの論文の定義に基づいています。[ 3 ]

変数の列があり、ある閾値に対して が成り立つことを確かめたいとします。許容される唯一の演算は、が少なくとも 2減少し、最大 1増加する演算です。一般性を失うことなく、 が2減少し、が 1 増加すると仮定できます。 ×け、…、×1{\displaystyle x_{k},\dots ,x_{1}}た私⩽け、×私⩽T{\displaystyle \forall i\leqslant k,x_{i}\leqslant T}T{\displaystyle T}減らす（私）{\displaystyle {\text{削減}}(i)}×私{\displaystyle x_{i}}xi+1{\displaystyle x_{i+1}}REDUCE(i){\displaystyle {\text{REDUCE}}(i)}xi{\displaystyle x_{i}}xi+1{\displaystyle x_{i+1}}

a が1増加した場合、ガイドの目的は、閾値を遵守するためにどのインデックスに適用すべきかを伝えることです。ガイドは、増加ごとに関数 を呼び出すことのみが許可されます。xj{\displaystyle x_{j}}i{\displaystyle i}REDUCE(i){\displaystyle {\text{REDUCE}}(i)}O(1){\displaystyle O(1)}REDUCE{\displaystyle {\text{REDUCE}}}

ガイドは、および となる別のシーケンスにアクセスできます。 の増加後に となる限り、は より「はるかに」下なので、ガイドに助けを求める必要はありません。しかし、の増加前であれば、変更後に となります。 xk′,…,x1′{\displaystyle x'_{k},\dots ,x'_{1}}xi⩽xi′{\displaystyle x_{i}\leqslant x'_{i}}xi′∈{T−2,T−1,T}{\displaystyle x'_{i}\in \{T-2,T-1,T\}}xj{\displaystyle x_{j}}xj⩽xj′{\displaystyle x_{j}\leqslant x'_{j}}xj{\displaystyle x_{j}}T{\displaystyle T}xj=xj′{\displaystyle x_{j}=x'_{j}}xj+1>xj′{\displaystyle x_{j}+1>x'_{j}}

説明を簡略化するために、 と仮定し、 とします。ガイドは、が存在しないことを許容する形で、 のシーケンスにブロックを作成します。ガイドは、ブロックに含まれない各要素は または のいずれかであるという不変条件を維持します。例えば、 のシーケンスのブロックは次のとおりです。 T=2{\displaystyle T=2}xi′∈{0,1,2}{\displaystyle x'_{i}\in \{0,1,2\}}xi′{\displaystyle x'_{i}}2,1,1,…,1,0{\displaystyle 2,1,1,\dots ,1,0}1{\displaystyle 1}1{\displaystyle 1}0{\displaystyle 0}xi′{\displaystyle x'_{i}}

1,2,1,1,0_,1,1,2,0_,2,0_,1,0,2,1,0_{\textstyle 1,{\underline {2,1,1,0}},1,1,{\underline {2,0}},{\underline {2,0}},1,0,{\underline {2,1,0}}}

ガイドは3つの配列で構成されています :

  • x{\displaystyle x}の配列xk,…,x1{\displaystyle x_{k},\dots ,x_{1}}
  • x′{\displaystyle x'}の配列xk′,…,x1′{\displaystyle x'_{k},\dots ,x'_{1}}
  • p{\displaystyle p}同じブロック内にあるすべてのポインタが、値を含む同じメモリセルを指すポインタ配列。aがブロック内にない場合は、a は値を含むメモリセルを指します。pi{\displaystyle p_{i}}xi′{\displaystyle x'_{i}}xi′{\displaystyle x'_{i}}pi{\displaystyle p_{i}}⊥{\displaystyle \bot }

この定義によれば、ガイドには 2 つの重要な特性があります。

  1. ブロック内の各要素について、時間内にブロックの最も左の要素を見つけることができます。O(1){\displaystyle O(1)}
  2. ブロックの各要素が指すメモリセルに割り当てることで、時間内にブロックを破棄できます。O(1){\displaystyle O(1)}⊥{\displaystyle \bot }

この方法により、ガイドはどのインデックスを時間内に選択するかを決定できます。以下に例を示します。 REDUCE{\displaystyle {\text{REDUCE}}}O(1){\displaystyle O(1)}

2,1,1,0_,2,1,1,1,0_2,1,1,0_,2,2,1,1,0_Increment xi′2,1,1,1_,0,2,1,1,0_REDUCE2,1,1,1_,1,0,1,1,0_REDUCE2,1,1,1,1,0_,1,1,0reestablish blocks{\displaystyle {\begin{array}{ll}{\underline {2,1,1,0}},{\underline {2,1,1,1,0}}&\\{\underline {2,1,1,0}},{\underline {2,{\color {red}2},1,1,0}}&{\text{Increment }}x'_{i}\\{\underline {2,1,1,{\color {green}1}}},{\underline {{\color {blue}0},2,1,1,0}}&{\text{REDUCE}}\\{\underline {2,1,1,1}},{\underline {{\color {green}1},{\color {blue}0},1,1,0}}&{\text{REDUCE}}\\{\underline {2,1,1,1,1,0}},1,1,0&{\text{reestablish blocks}}\\\end{array}}}

ブロックを再確立するために、最初のブロックに追加された1と0のポインタは、最初のブロックの他のすべての要素と同じセルを指すようになり、2番目のブロックのセルの値は に変更されます。前の例では、必要な操作は2つだけでした。これは実際にはすべてのインスタンスに当てはまります。したがって、キューに必要な操作は、プロパティを再確立する操作のみです。 ⊥{\displaystyle \bot }REDUCE{\displaystyle {\text{REDUCE}}}O(1){\displaystyle O(1)}

ブロダルキューの操作

さまざまな優先キュー操作を実装するには、まずツリーのいくつかの重要な変換を記述する必要があります。

変革

リンクツリー

木をリンクするには、ランクが等しい3つのノードが必要です。これら3つのノードの最小値は、2回の比較で計算できます。ここでは が最小値であると仮定していますが、このプロセスはすべての に対して同様です。これで、 ノードと左端の2つの子をの にし、 のランクを1上げることができます。これにより、と のすべての不変条件が維持されます。 x1,x2 and x3{\displaystyle x_{1},x_{2}{\text{ and }}x_{3}}x1{\displaystyle x_{1}}xi{\displaystyle x_{i}}x2{\displaystyle x_{2}}x3{\displaystyle x_{3}}x1{\displaystyle x_{1}}x1{\displaystyle x_{1}}RANK{\displaystyle {\text{RANK}}}SETS{\displaystyle {\text{SETS}}}

ツリーのリンク解除

にランク の息子がちょうど2つまたは3つある場合、これらの息子を削除して、新たに最大の息子のランクに1を加えたランクを取得できます。条件から、不変条件が保持されることがわかります。これにより、すべてのおよび不変条件が満たされます。に4つ以上の子がある場合、そのうち2つを削除するだけで、すべての不変条件が満たされます。したがって、ランク のツリーのリンクを解除すると、常にランク のツリーが2つまたは3つ（削除された2つまたは3つの子から）作成され、ランク のツリーが最大で1つ追加されます。 x{\displaystyle x}rank(x)−1{\displaystyle {\text{rank}}(x)-1}x{\displaystyle x}ARITY-BOUND{\displaystyle {\text{ARITY-BOUND}}}NEXT-RANK-ARITY{\displaystyle {\text{NEXT-RANK-ARITY}}}RANK{\displaystyle {\text{RANK}}}SETS{\displaystyle {\text{SETS}}}x{\displaystyle x}k{\displaystyle k}k−1{\displaystyle k-1}k{\displaystyle k}

根の息子たちの維持

根の子を追加したり削除したりする場合、不変条件が成り立つようにする必要があります。そのために、根とそれぞれに2つずつ、計4つのガイドを使用します。 の子に一定時間でアクセスできるように、各階数に階数の の子へのポインタを持つ、 の拡張可能な配列を作成します。一方のガイドは という条件を維持し、もう一方のガイドはに対して両方の条件を維持します。階数 との の子は、その数が2から7の間になるように、個別に直接処理されます。ガイドの定義における変数に相当するものは、上限ガイドの値と下限ガイドの値を持ちます。 ROOT-RANK{\displaystyle {\text{ROOT-RANK}}}t1{\displaystyle t_{1}}t2{\displaystyle t_{2}}t1{\displaystyle t_{1}}i∈{0,…,rank(t1)−1}{\displaystyle i\in \{0,\dots ,{\text{rank}}(t_{1})-1\}}t1{\displaystyle t_{1}}i{\displaystyle i}arityi(t1)⩽7{\displaystyle {\text{arity}}_{i}(t_{1})\leqslant 7}arityi(t1)⩾2{\displaystyle {\text{arity}}_{i}(t_{1})\geqslant 2}i∈{0,…,rank(t1)−3}{\displaystyle i\in \{0,\dots ,{\text{rank}}(t_{1})-3\}}t1{\displaystyle t_{1}}rank(t1)−1{\displaystyle {\text{rank}}(t_{1})-1}rank(t1)−2{\displaystyle {\text{rank}}(t_{1})-2}xi′{\displaystyle x'_{i}}{5,6,7}{\displaystyle \{5,6,7\}}{4,3,2}{\displaystyle \{4,3,2\}}

この文脈では、ランク の子をルートに追加すると、1 増加し、演算を適用します。ここでの演算は、ランク の 3 つのツリーをリンクして、ランク の新しい子を作成するというものです。したがって、 3 を減らし、 1 を増やします。この増加によってランク の子が多すぎる場合、またはこれらの子の一部をリンクして のランクを増やす可能性がある場合、 のランクを増やす必要があります。 のランクを増やすと、ガイドによって管理される拡張可能な配列の長さを増やす必要があります。 i{\displaystyle i}xi′{\displaystyle x'_{i}}REDUCE{\displaystyle {\text{REDUCE}}}RECUCE(i){\displaystyle {\text{RECUCE}}(i)}i{\displaystyle i}i+1{\displaystyle i+1}arityi(t1){\displaystyle {\text{arity}}_{i}(t_{1})}arityi+1(t1){\displaystyle {\text{arity}}_{i+1}(t_{1})}rank(t1)−2{\displaystyle {\text{rank}}(t_{1})-2}rank(t1)−1{\displaystyle {\text{rank}}(t_{1})-1}t1{\displaystyle t_{1}}t1{\displaystyle t_{1}}

息子を切り離す操作も非常に似ていますが、ここでは操作がツリーのリンク解除に相当します。 t1{\displaystyle t_{1}}REDUCE{\displaystyle {\text{REDUCE}}}

ルートについても状況はほぼ同じです。ただし、 はが最小元であることを保証するので、 の子を連結または連結解除しても違反は発生しないとわかります。 については同じことは言えません。息子を連結しても新しい違反は発生しませんが、息子を連結解除すると最大 3 つの新しい違反が発生する可能性があります。連結解除によって残された木は、ランクが より小さい場合はの息子になり、それ以外の場合は の息子になります。ランクが より大きい新しい違反はに追加されます。セット (つまりと)の不変量を維持するために、 のランクが増加され、それらの不変量に​​おいて が十分に大きく選択される ことを保証する必要があります。t2{\displaystyle t_{2}}MINIMUM-NODE{\displaystyle {\text{MINIMUM-NODE}}}t1{\displaystyle t_{1}}t1{\displaystyle t_{1}}t2{\displaystyle t_{2}}t1{\displaystyle t_{1}}rank(t1){\displaystyle {\text{rank}}(t_{1})}t2{\displaystyle t_{2}}rank(t1){\displaystyle {\text{rank}}(t_{1})}V(t1){\displaystyle V(t_{1})}V(t1){\displaystyle V(t_{1})}V-RANK-BOUND{\displaystyle {\text{V-RANK-BOUND}}}V-SIZE-BOUND{\displaystyle {\text{V-SIZE-BOUND}}}t1{\displaystyle t_{1}}α{\displaystyle \alpha }

違反の削減

この変革の目標は、潜在的な違反の総量を削減すること、つまり を削減することです。 |⋃x∈T1∪T2V(x)∪W(x)|{\displaystyle \left|\bigcup _{x\in T_{1}\cup T_{2}}V(x)\cup W(x)\right|}

2つの潜在的な違反と、同じランクの違反があると仮定します。この場合、いくつかのケースが考えられます。 x1{\displaystyle x_{1}}x2{\displaystyle x_{2}}k{\displaystyle k}

  1. いずれかのノードが違反ではないことが判明した場合は、対応する違反セットからそのノードを削除するだけです。
  2. それ以外の場合、両方のノードは違反です。 により、 と の両方に少なくとも1つの兄弟ノードがある ことがわかります。次に、ARITY-BOUND{\displaystyle {\text{ARITY-BOUND}}}x1{\displaystyle x_{1}}x2{\displaystyle x_{2}}
    1. と が兄弟でない場合、一般性を失うことなく と仮定することができ、とをルートとするサブツリーを交換できます。 違反の数は、この交換中にのみ減少します。x1{\displaystyle x_{1}}x2{\displaystyle x_{2}}parent(x1)⩽parent(x2){\displaystyle {\text{parent}}(x_{1})\leqslant {\text{parent}}(x_{2})}x1{\displaystyle x_{1}}x2{\displaystyle x_{2}}
    2. それ以外の場合、およびは と呼ぶノードの兄弟です。 x1{\displaystyle x_{1}}x2{\displaystyle x_{2}}y{\displaystyle y}
      1. にランク の兄弟が複数存在する場合、前のサブセクションで説明したように、切り離しての違反しないノードにすることができます。x1{\displaystyle x_{1}}k{\displaystyle k}x1{\displaystyle x_{1}}t1{\displaystyle t_{1}}
      2. それ以外の場合、および は、ランクの唯一の子です。 x1{\displaystyle x_{1}}x2{\displaystyle x_{2}}k{\displaystyle k}y{\displaystyle y}
        1. ならば、 と の両方のノードを から切り離し、前の節で説明したようにの違反のないノードにすることができます。rank(y)>k+1{\displaystyle {\text{rank}}(y)>k+1}x1{\displaystyle x_{1}}x2{\displaystyle x_{2}}y{\displaystyle y}t1{\displaystyle t_{1}}
        2. それ以外の場合、を切り捨てます。の新しいランクは、その左端の息子のランクに1を加えたものになります。 をランクの息子で置き換えます。これは前の節で説明したように切り捨てることができます。 の置き換えがランク の違反ノードになった場合は、それを に追加します。最後に、上記のようにの新しい息子を作成します。rank(y)=k+1{\displaystyle {\text{rank}}(y)=k+1}x1,x2 and y{\displaystyle x_{1},x_{2}{\text{ and }}y}y{\displaystyle y}y{\displaystyle y}t1{\displaystyle t_{1}}k+1{\displaystyle k+1}y{\displaystyle y}k+1{\displaystyle k+1}W(t1){\displaystyle W(t_{1})}x1,x2 and y{\displaystyle x_{1},x_{2}{\text{ and }}y}t1{\displaystyle t_{1}}

違反を多く避ける

違反を追加する違反集合はとのみです。前述のように、これらの集合の不変量はガイドを用いて維持されます。 に違反を追加する場合、以下の2つのケースが考えられます。 V(t1){\displaystyle V(t_{1})}W(t1){\displaystyle W(t_{1})}W(t1){\displaystyle W(t_{1})}

  1. 指定されたランクの違反がちょうど 6 個あり、 の子ではない違反ノードが少なくとも 2 つある場合、ガイドによって指定された操作を適用します。t2{\displaystyle t_{2}}REDUCE{\displaystyle {\text{REDUCE}}}
  2. の息子である違反が4つ以上ある場合、追加の違反を切り捨て、 の下にリンクします。これにより、これらのノードによって生成された違反が削除され、 の息子を維持するガイドには影響しません。t2{\displaystyle t_{2}}t1{\displaystyle t_{1}}t2{\displaystyle t_{2}}

実行される各優先キュー操作について、 の一定数の息子を に移動することにより、 のランクを少なくとも 1増やします( の場合)。 のランクを増やすと、すべての不変条件を維持しながら に違反を追加できます。および の場合、の最大の息子を切り取り、それらを にリンクして の息子を作成できます。これにより、すべての不変条件が満たされます。それ以外の場合は、ランク のの息子を切り取り、この息子のリンクを解除して、結果として得られるツリーを に追加します。 の場合、 が最大ランクのノードであることがわかっているため、大きな違反は作成できないことがわかります。 t1{\displaystyle t_{1}}t2{\displaystyle t_{2}}t1{\displaystyle t_{1}}T2≠∅{\displaystyle T_{2}\neq \emptyset }t1{\displaystyle t_{1}}V(t1){\displaystyle V(t_{1})}T2≠∅{\displaystyle T_{2}\neq \emptyset }rank(t2)⩽rank(t1)+2{\displaystyle {\text{rank}}(t_{2})\leqslant {\text{rank}}(t_{1})+2}t2{\displaystyle t_{2}}t1{\displaystyle t_{1}}t2{\displaystyle t_{2}}t1{\displaystyle t_{1}}t2{\displaystyle t_{2}}rank(t1)+2{\displaystyle {\text{rank}}(t_{1})+2}t1{\displaystyle t_{1}}T2=∅{\displaystyle T_{2}=\emptyset }t1{\displaystyle t_{1}}

優先キュー操作

キューを作成する

MakeQueue(){\displaystyle {\text{MakeQueue}}()}空のツリーのペアを返すだけです。

最小値を検索

FindMin(Q){\displaystyle {\text{FindMin}}(Q)}を返します。 t1{\displaystyle t_{1}}

入れる

Insert(Q,e){\displaystyle {\text{Insert}}(Q,e)}はの特殊なケースに過ぎず、はとのみを含むキューです。 Meld(Q1,Q2){\displaystyle {\text{Meld}}(Q_{1},Q_{2})}Q2{\displaystyle Q_{2}}e{\displaystyle e}Q1=Q{\displaystyle Q_{1}=Q}

メルド

Meld(Q1,Q2){\displaystyle {\text{Meld}}(Q_{1},Q_{2})}には4つのツリー（キューごとに2つ）が含まれます。最小ルートを持つツリーが新しいツリーになります。このツリーが最大ランクのツリーでもある場合は、前述のように、他のすべてのツリーをその下に追加できます。この場合、違反ノードは作成されないため、違反ノードに対して変換は行われません。それ以外の場合は、最大ランクのツリーが新しいツリーになり、他のツリーは「ルートの子の維持」セクションで説明したように、その下に追加されます。この新しい と同じランクのツリーがある場合は、追加する前にそれらのツリーのリンクを解除できます。発生した違反は、「違反が多すぎるのを避ける」セクションで説明したように処理されます。 T1{\displaystyle T_{1}}T2{\displaystyle T_{2}}T2{\displaystyle T_{2}}

減少キー

DecreaseKey(Q,e,e′){\displaystyle {\text{DecreaseKey}}(Q,e,e')}の要素を で（ で）置き換えます。 の場合、2つのノードを交換します。それ以外の場合は、「違反の多発を防ぐ」セクションで説明したように、潜在的な新しい違反を処理します。 e{\displaystyle e}e′{\displaystyle e'}e′⩽e{\displaystyle e'\leqslant e}e′<t1{\displaystyle e'<t_{1}}

最小値を削除

DeleteMin(Q){\displaystyle {\text{DeleteMin}}(Q)}は、最悪の場合 かかることが許されています。まず、のすべての子を に移動して完全に空にし、のランク 0 の子を作成します。次にを削除すると、最大で 個の独立したツリーが残ります。次に、古いルートの違反セットを調べ、新しいツリーのすべてのルートを調べることで、新しい最小値が見つかります。最小要素がルートでない場合は、同じランクのツリーからルートをスワップできます。これにより、最大で 1 つの違反が作成されます。次に、リンク操作とデリンク操作を実行して、独立したツリーを新しい最小要素の子にします。これにより、と の不変条件が再確立されます。新しいルートのとセットを古いルートの と セットとマージすることで、サイズ の新しい違反セットが 1 つ得られます。最大で違反を減らす変換を行うことで、違反セットに各ランクの要素が最大で 1 つだけ含まれるようにすることができます。このセットが新しいセットになり、新しいセットは空です。これにより、不変条件が再確立されます。また、新しいルート の新しいガイドを初期化する必要があります。 O(log⁡n){\displaystyle O(\log n)}T2{\displaystyle T_{2}}t2{\displaystyle t_{2}}t1{\displaystyle t_{1}}t2{\displaystyle t_{2}}t1{\displaystyle t_{1}}t1{\displaystyle t_{1}}O(log⁡n){\displaystyle O(\log n)}O(log⁡n){\displaystyle O(\log n)}RANK{\displaystyle {\text{RANK}}}ROOTS{\displaystyle {\text{ROOTS}}}V{\displaystyle V}W{\displaystyle W}V{\displaystyle V}W{\displaystyle W}O(log⁡n){\displaystyle O(\log n)}O(log⁡n){\displaystyle O(\log n)}W{\displaystyle W}V{\displaystyle V}SETS{\displaystyle {\text{SETS}}}t1{\displaystyle t_{1}}

消去

ここで、 は最小の要素を表します。は、 を呼び出して、を続けるだけで簡単に実装できます。 −∞{\displaystyle -\infty }Delete(Q,e){\displaystyle {\text{Delete}}(Q,e)}DecreaseKey(Q,e,−∞){\displaystyle {\text{DecreaseKey}}(Q,e,-\infty )}DeleteMin(Q){\displaystyle {\text{DeleteMin}}(Q)}

実装の詳細

このセクションでは、Brodal Queue データ構造の実装の詳細をまとめます。

各ツリーでは、各ノードは次のフィールドを持つレコードです。

  • ノードに関連付けられた要素（その値）
  • ノードのランク、
  • ノードの左と右の兄弟へのポインタ、
  • 父ノードへのポインタ、
  • 左端の息子へのポインタ、
  • ノードの最初の要素へのポインタとセット、V{\displaystyle V}W{\displaystyle W}
  • ノードが属する違反セット内の次の要素と前の要素へのポインタ。このノードが違反セットの最初のノードであるか、またはこのノードが属する違反セットの最初のノードである場合、前のポインタは を指します。V(x){\displaystyle V(x)}W(x){\displaystyle W(x)}x{\displaystyle x}
  • ランク のの息子へのポインタの配列（ を含む）、t1{\displaystyle t_{1}}i{\displaystyle i}i∈{0,…,rank(t1)−1}{\displaystyle i\in \{0,\dots ,{\text{rank}}(t_{1})-1\}}
  • の同様の配列、t2{\displaystyle t_{2}}
  • ランク のノードへのポインタの配列( を含む)。W(t1){\displaystyle W(t_{1})}i{\displaystyle i}i∈{0,…,rank(t1)−1}{\displaystyle i\in \{0,\dots ,{\text{rank}}(t_{1})-1\}}

最終的に、 、 の上限を維持するためのガイドが 3 つ、、の下限を維持するためのガイドが 2 つあります。 arityi(t1){\displaystyle {\text{arity}}_{i}(t_{1})}arityi(t2){\displaystyle {\text{arity}}_{i}(t_{2})}wi(t1){\displaystyle w_{i}(t_{1})}arityi(t1){\displaystyle {\text{arity}}_{i}(t_{1})}arityi(t2){\displaystyle {\text{arity}}_{i}(t_{2})}

Brodal Queueは、管理すべきポインタと集合が膨大であるため、実装が非常に困難です。そのため、ダイクストラ法のようなアルゴリズムの時間計算量を削減するための純粋に理論的なオブジェクトとして説明されるのが適切です。しかしながら、BrodalはScalaで実装されています（GitHubリポジトリはこちら：https://github.com/ruippeixotog/functional-brodal-queues）。Gerth Stølting Brodalは論文の中で、「今後の重要な課題は、構築を簡素化して実用化できるようにすることだ」と述べています。[ 3 ]

実行時間の概要

様々なヒープデータ構造の時間計算量[ 4 ]を以下に示します。略語am.は、与えられた計算量が償却されることを示し、そうでない場合は最悪ケースの計算量です。「 O ( f ) 」および「Θ ( f ) 」の意味については、Big O記法を参照してください。演算名は最小ヒープを前提としています。

手術 最小値を見つける 削除最小値 減少キー 入れる 融合する ヒープを作る[ a ]
バイナリ[ 4 ]Θ (1) Θ (log  n ) Θ (log  n ) Θ (log  n ) Θ ( n ) Θ ( n )
スキュー[ 5 ]Θ (1) O (log  n )午前。O (log  n )午前。O (log  n )午前。O (log  n )午前。Θ ( n )午前。
左翼[ 6 ]Θ (1) Θ (log  n ) Θ (log  n ) Θ (log  n ) Θ (log  n ) Θ ( n )
二項分布[ 4 ] [ 8 ]Θ (1) Θ (log  n ) Θ (log  n ) Θ（１）午前。Θ (log  n ) [ b ]Θ ( n )
歪んだ二項分布[ 9 ]Θ (1) Θ (log  n ) Θ (log  n ) Θ (1) Θ (log  n ) [ b ]Θ ( n )
2～3山[ 11 ]Θ (1) O (log  n )午前。Θ (1) Θ（１）午前。O (log  n ) [ b ]Θ ( n )
ボトムアップの歪み[ 5 ]Θ (1) O (log  n )午前。O (log  n )午前。Θ（１）午前。Θ（１）午前。Θ ( n )午前。
ペアリング[ 12 ]Θ (1) O (log  n )午前。o (log  n ) am. [ c ]Θ (1) Θ (1) Θ ( n )
ランクペアリング[ 15 ]Θ (1) O (log  n )午前。Θ（１）午前。Θ (1) Θ (1) Θ ( n )
フィボナッチ[ 4 ] [ 16 ]Θ (1) O (log  n )午前。Θ（１）午前。Θ (1) Θ (1) Θ ( n )
厳密なフィボナッチ[ 17 ] [ d ]Θ (1) Θ (log  n ) Θ (1) Θ (1) Θ (1) Θ ( n )
ブロダル[ 18 ] [ d ]Θ (1) Θ (log  n ) Θ (1) Θ (1) Θ (1) Θ ( n ) [ 19 ]
  1. ^ make-heapは、 n 個の未ソート要素のシーケンスからヒープを構築する操作です。meld がO (log  n ) 時間で実行される場合、 make-heapはΘ ( n ) 時間で実行できます（ただし、両方の計算量は償却可能です）。 [ 5 ] [ 6 ]別のアルゴリズムでは、バイナリヒープに対してΘ ( n )時間。 [ 7 ]
  2. ^ a b c永続ヒープ（ decrece-keyをサポートしない）の場合、一般的な変換により、 meldのコストが挿入のコストまで削減されます。delete -minの新しいコストは、 delete-minとmeldの古いコストの合計になります。[ 10 ]ここで、meldはΘ (1)時間（挿入のコストが償却される場合）で実行されますが、 delete-minは依然としてO (log  n )で実行されます。これを歪んだ二項ヒープに適用すると、最悪のケースの複雑さが最適な永続ヒープであるBrodal-Okasakiキューが生成されます。[ 9 ]
  3. ^ [ 13 ]の下限値[ 14 ]の上限値Ω(log⁡log⁡n),{\displaystyle \Omega (\log \log n),}O(22log⁡log⁡n).{\displaystyle O(2^{2{\sqrt {\log \log n}}}).}
  4. ^ a b Brodalキューと厳密なフィボナッチヒープは、ヒープの最悪ケース計算量を最適化する。これらは当初、命令型データ構造として記述された。Brodal-Okasakiキューは、減少キーがサポートされていないことを除いて、同様の最適化を実現する永続的データ構造である。

ゲルト・ストルティング・ブロダル

Gerth Stølting Brodal は、デンマークのオーフス大学の教授です。[ 20 ]彼は Brodal キューで最もよく知られています。

参考文献

  1. ^ a b Gerth Stølting Brodal (1996). 最悪ケースにおける効率的な優先キュー. 第7回ACM-SIAM離散アルゴリズムシンポジウム講演論文集, pp. 52–58
  2. ^ Gerth Stølting BrodalとChris Okasaki (1996).最適な純粋機能的優先キュー. Journal of Functional Programming.
  3. ^ a b Brodal, Gerth Stølting (1996). 「最悪ケースの効率的な優先キュー」(PDF) .{{cite web}}: CS1 maint: url-status (link)
  4. ^ a b c dコーメン、トーマス H. ;チャールズ・E・ライザーソン;リベスト、ロナルド L. (1990)。アルゴリズム入門(第 1 版)。 MIT プレスとマグロウヒル。ISBN 0-262-03141-8。
  5. ^ a b c Sleator, Daniel Dominic ; Tarjan, Robert Endre (1986年2月). 「自己調整ヒープ」 . SIAM Journal on Computing . 15 (1): 52– 69. CiteSeerX 10.1.1.93.6678 . doi : 10.1137/0215004 . ISSN 0097-5397 .  
  6. ^ a b Tarjan, Robert (1983). 「3.3. 左派ヒープ」.データ構造とネットワークアルゴリズム. pp.  38– 42. doi : 10.1137/1.9781611970265 . ISBN 978-0-89871-187-5。
  7. ^ Hayward, Ryan; McDiarmid, Colin (1991). 「繰り返し挿入によるヒープ構築の平均ケース分析」(PDF) . J. Algorithms . 12 : 126–153 . CiteSeerX 10.1.1.353.7888 . doi : 10.1016/0196-6774(91)90027-v . 2016年2月5日時点のオリジナル(PDF)からアーカイブ。 2016年1月28日閲覧。 
  8. ^ 「二項式ヒープ | Brilliant Math & Science Wiki」brilliant.org . 2019年9月30日閲覧。
  9. ^ a b Brodal, Gerth Stølting; Okasaki, Chris (1996年11月)、「最適な純粋機能的優先度キュー」、Journal of Functional Programming、6 (6): 839– 857、doi : 10.1017/s095679680000201x
  10. ^ Okasaki, Chris (1998). 「10.2. 構造的抽象化」.純粋関数型データ構造（第1版）. pp.  158– 162. ISBN 9780521631242。
  11. ^高岡忠雄(1999) 「2-3ヒープ理論」 (PDF)、p.12
  12. ^ Iacono, John (2000)、「ペアリングヒープの改良された上限値」、Proc. 7th Scandinavian Workshop on Algorithm Theory (PDF)、Lecture Notes in Computer Science、vol. 1851、Springer-Verlag、pp.  63– 77、arXiv : 1110.4428、CiteSeerX 10.1.1.748.7812、doi : 10.1007/3-540-44985-X_5、ISBN  3-540-67690-2
  13. ^ Fredman, Michael Lawrence (1999年7月). 「ペアリングヒープと関連データ構造の効率について」(PDF) . Journal of the Association for Computing Machinery . 46 (4): 473– 501. doi : 10.1145/320211.320214 .
  14. ^ペティ, セス (2005).ペアリングヒープの最終分析に向けて(PDF) . FOCS '05 Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science. pp.  174– 183. CiteSeerX 10.1.1.549.471 . doi : 10.1109/SFCS.2005.75 . ISBN  0-7695-2468-0。
  15. ^ハウプラー、ベルンハルト;セン、シッダールタ。タージャン、ロバート E. (2011 年 11 月)。「ランクペアリングヒープ」(PDF)。サイアム J. コンピューティング。40 (6): 1463 ～ 1485 年。土井: 10.1137/100785351。
  16. ^ Fredman, Michael Lawrence ; Tarjan, Robert E. (1987年7月). 「フィボナッチヒープと改良ネットワーク最適化アルゴリズムにおけるその利用」(PDF) . Journal of the Association for Computing Machinery . 34 (3): 596– 615. CiteSeerX 10.1.1.309.8927 . doi : 10.1145/28869.28874 . 
  17. ^ Brodal, Gerth Stølting ; Lagogiannis, George ; Tarjan, Robert E. (2012).厳密なフィボナッチヒープ(PDF) . Proceedings of the 44th symposium on Theory of Computing - STOC '12. pp.  1177– 1184. CiteSeerX 10.1.1.233.1740 . doi : 10.1145/2213977.2214082 . ISBN  978-1-4503-1245-5。
  18. ^ Brodal, Gerth S. (1996)、「最悪ケースの効率的な優先キュー」（PDF）、第7回ACM-SIAM離散アルゴリズムシンポジウム論文集、pp.  52– 58
  19. ^ Goodrich, Michael T. ; Tamassia, Roberto (2004). 「7.3.6. ボトムアップヒープ構築」. 『Javaにおけるデータ構造とアルゴリズム』（第3版）. pp.  338– 341. ISBN 0-471-46983-1。
  20. ^ “オーフス大学のガース・シュトルティング・ブローダルのウェブサイト” . 2016 年2 月 18 日に取得。
「 https://en.wikipedia.org/w/index.php?title=Brodal_queue&oldid=1333678769」から取得