ブロダルキュー

コンピュータサイエンスにおいて、ブロダルキューは、最悪時間制約が非常に小さいヒープ/優先度キュー構造である。${\displaystyle O(1)}$挿入、最小値の検索、結合（2 つのキューをマージ）、減少キー、${\displaystyle O(\mathrm {log} (n))}$削除最小値と一般削除の場合。これらは、運用コストの償却に頼らずにこれらの境界を達成した最初のヒープバリアントです。ブロダルキューは、その発明者であるゲルト・ストルティング・ブロダルにちなんで名付けられました。^{[ 1 ]}

他の優先度キュー構造よりも漸近的な境界は優れているものの、ブロダル自身が言うように「非常に複雑」であり、「実際には適用できない」。^{[ 1 ]}ブロダルと岡崎は、ブロダルキューの永続的（純粋関数型）バージョンについて述べている。 ^{[ 2 ]}

ブロダルキューは2つの木の集合である${\displaystyle T_{1}}$そして${\displaystyle T_{2}}$そして5つのガ​​イドがあります。ガイドデータ構造の定義は次のセクションで説明します。どちらのツリーでも、各ノードにはランクがあり、このランクは後の操作に役立ち、直感的にはノードを根とするサブツリーのサイズの対数に対応します。${\displaystyle {\text{arity}}_{i}(x)}$ノードの子ノードの数${\displaystyle x}$ランク付き${\displaystyle i}$また、$t1$木の根のために${\displaystyle T_{1}}$そして$t2$木の根のために${\displaystyle T_{2}}$。各時点において、ノードを根とするすべてのサブツリーは、次の 5 つの不変条件を満たす必要があります(これらは後ほど と呼ばれます) 。$\displaystyle {\text{ランク}}}$不変量):

• ${\displaystyle {\text{LEAF-RANK}}}$ ： もし${\displaystyle x}$葉っぱであれば、$\displaystyle {\text{rank}}(x)=0}$、
• ${\displaystyle {\text{親ランク}}}$ :$\displaystyle {\text{rank}}(x)<{\text{rank}}({\text{parent}}(x))}$、
• ${\displaystyle {\text{NEXT-RANK-ARITY}}}$ ： もし$\displaystyle {\text{rank}}(x)>0}$、 それから$\displaystyle \text{arity}}_{{\text{rank}}(x)-1}(x)\geqslant 2}$、
• ${\displaystyle {\text{アリティ制限}}}$:$\displaystyle \text{arity}}_{i}(x)\in \{0,2,3,\dots ,7\}}$私たちは、${\displaystyle {\text{arity}}_{i}(x)\neq 1}$、
• ${\displaystyle {\text{ルートランク}}}$ :${\displaystyle T_{2}=\emptyset }$または$\displaystyle {\text{rank}}(t_{1})\leqslant {\text{rank}}(t_{2})}$。

ここ${\displaystyle {\text{NEXT-RANK-ARITY}}}$ノードを根とする部分木のサイズは、そのノードのランクに対して少なくとも指数関数的であることを保証します。さらに、${\displaystyle {\text{アリティ制限}}}$は、与えられたノードの各ランクの子の数を制限します。これは、すべてのノードがランクと次数を持つことを意味します。${\displaystyle O(\log n)}$。

Brodalキューでは、すべてのノードが親ノードよりも大きな値を持つとは限りません。この条件に違反するノードは違反ノードと呼ばれます。しかし、違反ノードの数は比較的少なく抑えたいと考えます。違反ノードを追跡するために、各ノードに対して2つのセットを作成します。${\displaystyle V(x)}$そして${\displaystyle W(x)}$より大きいノード${\displaystyle x}$直感的に、${\displaystyle V(x)}$ノードはより大きいですか${\displaystyle x}$ランクが大きい（つまり、${\displaystyle y\in V(x)}$もし$\displaystyle {\text{rank}}(y)\geqslant {\text{rank}}(t_{1})}$）、 そして${\displaystyle W(x)}$ランクの小さいノードは（$\displaystyle {\text{rank}}(y)<{\text{rank}}(t_{1})}$これらのセットは二重リンクリストを使用して実装されているため、順序があります。特に、違反しているすべてのノードがに追加されます。${\displaystyle V(x)}$リストの先頭に追加され、違反しているノードはすべて追加されます。${\displaystyle W(x)}$同じランクのノードの隣に挿入されます。${\displaystyle w_{i}(x)}$ノードの数を表す${\displaystyle W(x)}$階級${\displaystyle i}$の${\displaystyle V(x)}$そして${\displaystyle W(x)}$リストはこれらの 5 つの不変条件を満たします (${\displaystyle {\text{セット}}}$不変量):

• $最小ノード$ :${\displaystyle t_{1}=\min(T_{1}\cup T_{2})}$
• ${\displaystyle {\text{条件違反}}}$ ： もし${\displaystyle y\in V(x)\cup W(x)}$それから${\displaystyle y\geqslant x}$
• ${\displaystyle {\text{親権侵害}}}$： もし${\displaystyle y<{\text{parent}}(y)}$するとノードが存在する${\displaystyle x\neq y}$そのため${\displaystyle y\in V(x)\cup W(x)}$
• ${\displaystyle {\text{Wランクバウンド}}}$:${\displaystyle w_{i}(x)\leqslant 6}$
• ${\displaystyle {\text{Vランクバウンド}}}$: 表記することで${\displaystyle V(x)=(v_{|V(x)|},\dots ,v_{2},v_{1})}$、 我々は持っています：$\displaystyle \text{rank}}(v_{i})\geqslant \left\lfloor {\frac {i-1}{\alpha }}\right\rfloor }$ある定数に対して${\displaystyle \alpha }$。

すべてのノードはランクを持っています${\displaystyle O(\log n)}$の${\displaystyle {\text{Wランクバウンド}}}$そして${\displaystyle {\text{Vランクバウンド}}}$、 全て${\displaystyle V(x)}$そして${\displaystyle W(x)}$サイズは${\displaystyle O(\log n)}$。

また、木の根の不変量もいくつかあります。${\displaystyle T_{1}}$そして${\displaystyle T_{2}}$:$t1$そして$t2$（${\displaystyle {\text{ルーツ}}}$不変量）。

• ${\displaystyle {\text{ルートアリティ}}}$ :$t_i ∈ {2,3,\dots ,7} (i ∈ {0,1,\dots ,rank(t_i)-1})$、
• ${\displaystyle {\text{V-SIZE-BOUND}}}$:${\displaystyle |V(x)|\leqslant \alpha {\text{ rank}}(t_{1})}$、
• ${\displaystyle {\text{W-ELEMENTS-RANK}}}$： もし${\displaystyle y\in W(t_{1})}$、 それから$\displaystyle {\text{rank}}(y)<{\text{rank}}(t_{1})}$。

の${\displaystyle {\text{V-SIZE-BOUND}}}$不変量は基本的に、ランクを上げると$t1$1つにつき、最大で${\displaystyle \alpha }$新たな「大きな」違反（ここで「大きな」とは高いランクを持つことを意味する）は、${\displaystyle {\text{Vランクバウンド}}}$不変。一方、${\displaystyle {\text{W-ELEMENTS-RANK}}}$不変条件は、すべての違反が${\displaystyle W(x)}$は「小さい」ので、この不変条件は定義に従って真である。${\displaystyle W}$不変条件を維持する${\displaystyle {\text{Wランクバウンド}}}$そして${\displaystyle {\text{ルートアリティ}}}$これは些細なことではなく、これらを維持するために私たちは${\displaystyle {\text{DecreaseKey}}}$次のセクションで定義するガイドを使用して実装できる操作。毎回、${\displaystyle {\text{DecreaseKey}}}$この作戦では、基本的に以下のことを行います 。

1. 新しい違反を追加${\displaystyle V(t_{1})}$または${\displaystyle W(t_{1})}$違反の程度に応じて。
2. 避けるために${\displaystyle V(t_{1})}$そして${\displaystyle W(t_{1})}$規模が大きくなりすぎないように、段階的に2種類の変換を行います。
   1. 息子たちを動かす$t2$に$t1$ランクを上げる$t1$
   2. 違反件数を減らす${\displaystyle W(t_{1})}$ランク違反2件を置き換えることによって${\displaystyle k}$階級違反1件${\displaystyle k+1}$

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

変数のシーケンスがあると仮定します${\displaystyle x_{k},\dots ,x_{1}}$そして私たちはそれを確実にしたいのです${\displaystyle \forall i\leqslant k,x_{i}\leqslant T}$ある閾値に対して${\displaystyle T}$許可されている唯一の操作は${\displaystyle {\text{削減}}(i)}$これは減少する${\displaystyle x_{i}}$少なくとも2倍になり、${\displaystyle x_{i+1}}$最大で 1 だけ。一般性を失うことなく、${\displaystyle {\text{削減}}(i)}$削減する${\displaystyle x_{i}}$2ずつ増加し、${\displaystyle x_{i+1}}$1による。

もし${\displaystyle x_{j}}$1つ増加すると、ガイドの目的はどのインデックスについて教えてくれるかです${\displaystyle i}$応募する${\displaystyle {\text{削減}}(i)}$しきい値を尊重するため。ガイドは、${\displaystyle O(1)}$への呼びかけ${\displaystyle {\text{削減}}}$各増加に対応する関数。

ガイドは別のシーケンスにアクセスできます${\displaystyle x'_{k},\dots ,x'_{1}}$そのため${\displaystyle x_{i}\leqslant x'_{i}}$そして${\displaystyle x'_{i}\in \{T-2,T-1,T\}}$増加後も${\displaystyle x_{j}}$我々は持っています${\displaystyle x_{j}\leqslant x'_{j}}$私たちはガイドに助けを求める必要はありません。${\displaystyle x_{j}}$「はるか下」${\displaystyle T}$しかし、もし${\displaystyle x_{j}=x'_{j}}$増加前は、${\displaystyle x_{j}+1>x'_{j}}$変更後。

説明を簡略化するために、次のように仮定できます。${\displaystyle T=2}$、 となることによって${\displaystyle x'_{i}\in \{0,1,2\}}$ガイドはブロックを次の順序で作成します。${\displaystyle x'_{i}}$形の${\displaystyle 2,1,1,\dots ,1,0}$私たちが許可する場所には${\displaystyle 1}$ガイドでは、ブロックに含まれていない各要素は、${\displaystyle 1}$または${\displaystyle 0}$例えば、次のようなシーケンスのブロックがあります。${\displaystyle x'_{i}}$。

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

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

• ${\displaystyle x}$配列${\displaystyle x_{k},\dots ,x_{1}}$
• ${\displaystyle x'}$配列${\displaystyle x'_{k},\dots ,x'_{1}}$
• ${\displaystyle p}$すべてのポインタの配列${\displaystyle p_{i}}$そのために${\displaystyle x'_{i}}$同じブロック内にある場合、同じメモリセルに値が含まれていることを示します。${\displaystyle x'_{i}}$ブロック内にない場合は、${\displaystyle p_{i}}$メモリセルを指し示します${\displaystyle \bot }$。

この定義に基づくと、ガイドには2つの重要な特性がある 。

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

このようにして、ガイドはどのインデックスを${\displaystyle {\text{REDUCE}}}$時間が経つにつれて${\displaystyle O(1)}$以下に例を示します 。

${\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 番目のブロックのセルの値は次のように変更されます。${\displaystyle \bot }$前の例では、${\displaystyle {\text{REDUCE}}}$操作が必要だったが、これは実際にはすべてのインスタンスに当てはまる。したがって、キューは${\displaystyle O(1)}$財産を再建するための活動。

さまざまな優先度キュー操作を実装するには、まずツリーに対するいくつかの基本的な変換について説明する必要があります。

このセクションでは、Brodal Queueデータ構造の実装に関する詳細をいくつかまとめます。

各ツリーにおいて、各ノードは以下のフィールドを持つレコードです。

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

最後に、5 つのガイドがあります。そのうち 3 つは上限を維持するためです。${\displaystyle {\text{arity}}_{i}(t_{1})}$、${\displaystyle {\text{arity}}_{i}(t_{2})}$そして${\displaystyle w_{i}(t_{1})}$そして2つは下限値を維持するため${\displaystyle {\text{arity}}_{i}(t_{1})}$そして${\displaystyle {\text{arity}}_{i}(t_{2})}$。

追跡すべきポインタとセットの数が多いため、Brodal Queue の実装は非常に困難です。そのため、Dijkstra アルゴリズムなどのアルゴリズムの時間計算量を削減するための純粋に理論的なオブジェクトとして説明するのが最適です。ただし、Brodal はScalaで実装されています( GitHubリポジトリはこちら: https://github.com/ruippeixotog/functional-brodal-queues )。Gerth Stølting Brodal は論文の中で、「今後の研究における重要な課題は、構築を簡素化して実際に適用できるようにすることである」と述べています。^{[ 3 ]}

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

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