ブロダルキュー

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

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

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

意味

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

${\text{LEAF-RANK}}$ :が葉である場合、 $x$ ${\text{rank}}(x)=0$
${\text{親ランク}}$ : 、 ${\text{rank}}(x)<{\text{rank}}({\text{parent}}(x))$
${\text{NEXT-RANK-ARITY}}$ :ならば、 ${\text{rank}}(x)>0$ ${\text{arity}}_{{\text{rank}}(x)-1}(x)\geqslant 2$
${\text{ARITY-BOUND}}$ :私たちは、 ${\text{arity}}_{i}(x)\in \{0,2,3,\dots ,7\}$ ${\text{arity}}_{i}(x)\neq 1$
${\text{ルートランク}}$ ：または。 $T_{2}=\emptyset$ ${\text{rank}}(t_{1})\leqslant {\text{rank}}(t_{2})$

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

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

${\text{最小ノード}}$ : $t_{1}=\min(T_{1}\cup T_{2})$
${\text{条件違反}}$ : もしそうなら $y\in V(x)\cup W(x)$ $y\geqslant x$
${\text{親権を侵害する}}$ :すると、次のようなノードが存在する。 $y<{\text{parent}}(y)$ $x\neq y$ $y\in V(x)\cup W(x)$
${\text{Wランク境界}}$ : $w_{i}(x)\leqslant 6$
${\text{Vランク境界}}$ : と表記すると、次の関係が成り立ちます。特定の定数に対して。 $V(x)=(v_{|V(x)|},\dots ,v_{2},v_{1})$ ${\text{rank}}(v_{i})\geqslant \left\lfloor {\frac {i-1}{\alpha }}\right\rfloor$ $\alpha$

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

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

${\text{ルートアリティ}}$ : 、 $t_{i}\in \{2,3,\dots ,7\}{\text{ }}i\in \{0,1,\dots ,{\text{rank}}(t_{i})-1\}$
${\text{V-SIZE-BOUND}}$ : 、 $|V(x)|\leqslant \alpha {\text{rank}}(t_{1})$
${\text{W-ELEMENTS-RANK}}$ : ならば、。 $y\in W(t_{1})$ ${\text{rank}}(y)<{\text{rank}}(t_{1})$

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

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

ガイドデータ構造

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

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

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

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

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

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

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

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

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

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

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

${\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つだけでした。これは実際にはすべてのインスタンスに当てはまります。したがって、キューに必要な操作は、プロパティを再確立する操作のみです。 $\bot$ ${\text{REDUCE}}$ $O(1)$

ブロダルキューの操作

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

変革

リンクツリー

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

ツリーのリンク解除

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

根の息子たちの維持

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

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

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

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

違反の削減

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

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

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

違反を多く避ける

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

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

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

優先キュー操作

キューを作成する

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

最小値を検索

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

入れる

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

メルド

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

減少キー

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

最小値を削除

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

消去

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

実装の詳細

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

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

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

最終的に、、の上限を維持するためのガイドが 3 つ、、の下限を維持するためのガイドが 2 つあります。 ${\text{arity}}_{i}(t_{1})$ ${\text{arity}}_{i}(t_{2})$ $w_{i}(t_{1})$ ${\text{arity}}_{i}(t_{1})$ ${\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 ]}

^ make-heapは、 n 個の未ソート要素のシーケンスからヒープを構築する操作です。meld がO (log n ) 時間で実行される場合、 make-heapはΘ ( n ) 時間で実行できます^{（ただし、両方の計算量は償却可能です）。 [}⁵^]^[⁶^]別のアルゴリズムでは、バイナリヒープに対してΘ ( n )時間。^[⁷^]
^ ^a ^b ^c永続ヒープ（ decrece-keyをサポートしない）の場合、一般的な変換により、 meldのコストが挿入のコストまで削減されます。delete -minの新しいコストは、 delete-minとmeldの古いコストの合計になります。^[¹⁰^]ここで、meldはΘ (1)時間（挿入のコストが償却される場合）で実行されますが、 delete-minは依然としてO (log n )で実行されます。これを歪んだ二項ヒープに適用すると、最悪のケースの複雑さが最適な永続ヒープであるBrodal-Okasakiキューが生成されます。^[⁹^]
^ ^[¹³^]の下限値^[¹⁴^]の上限値 $\Omega (\log \log n),$ $O(2^{2{\sqrt {\log \log n}}}).$
^ ^a ^b Brodalキューと厳密なフィボナッチヒープは、ヒープの最悪ケース計算量を最適化する。これらは当初、命令型データ構造として記述された。Brodal-Okasakiキューは、減少キーがサポートされていないことを除いて、同様の最適化を実現する永続的データ構造である。

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

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

参考文献

^ ^a ^b Gerth Stølting Brodal (1996). 最悪ケースにおける効率的な優先キュー. 第7回ACM-SIAM離散アルゴリズムシンポジウム講演論文集, pp. 52–58
^ Gerth Stølting BrodalとChris Okasaki (1996).最適な純粋機能的優先キュー. Journal of Functional Programming.
^ ^a ^b Brodal, Gerth Stølting (1996). 「最悪ケースの効率的な優先キュー」(PDF) .{{cite web}}: CS1 maint: url-status (link)
^ ^a ^b ^c ^dコーメン、トーマス H. ;チャールズ・E・ライザーソン;リベスト、ロナルド L. (1990)。アルゴリズム入門(第 1 版)。 MIT プレスとマグロウヒル。ISBN 0-262-03141-8。
^ ^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 .
^ ^a ^b Tarjan, Robert (1983). 「3.3. 左派ヒープ」.データ構造とネットワークアルゴリズム. pp. 38– 42. doi : 10.1137/1.9781611970265 . ISBN 978-0-89871-187-5。
^ 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日閲覧。
^ 「二項式ヒープ | Brilliant Math & Science Wiki」brilliant.org . 2019年9月30日閲覧。
^ ^a ^b Brodal, Gerth Stølting; Okasaki, Chris (1996年11月)、「最適な純粋機能的優先度キュー」、Journal of Functional Programming、6 (6): 839– 857、doi : 10.1017/s095679680000201x
^ Okasaki, Chris (1998). 「10.2. 構造的抽象化」.純粋関数型データ構造（第1版）. pp. 158– 162. ISBN 9780521631242。
^高岡忠雄(1999) 「2-3ヒープ理論」 (PDF)、p.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
^ Fredman, Michael Lawrence (1999年7月). 「ペアリングヒープと関連データ構造の効率について」(PDF) . Journal of the Association for Computing Machinery . 46 (4): 473– 501. doi : 10.1145/320211.320214 .
^ペティ, セス (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。
^ハウプラー、ベルンハルト;セン、シッダールタ。タージャン、ロバート E. (2011 年 11 月)。「ランクペアリングヒープ」(PDF)。サイアム J. コンピューティング。40 (6): 1463 ～ 1485 年。土井: 10.1137/100785351。
^ 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 .
^ 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。
^ Brodal, Gerth S. (1996)、「最悪ケースの効率的な優先キュー」（PDF）、第7回ACM-SIAM離散アルゴリズムシンポジウム論文集、pp. 52– 58
^ Goodrich, Michael T. ; Tamassia, Roberto (2004). 「7.3.6. ボトムアップヒープ構築」. 『Javaにおけるデータ構造とアルゴリズム』（第3版）. pp. 338– 341. ISBN 0-471-46983-1。
^ “オーフス大学のガース・シュトルティング・ブローダルのウェブサイト” . 2016 年2 月 18 日に取得。

[8] make-heapは、 n 個の未ソート要素のシーケンスからヒープを構築する操作です。meld がO (log n ) 時間で実行される場合、 make-heapはΘ ( n ) 時間で実行できます^{（ただし、両方の計算量は償却可能です）。 [}⁵^]^[⁶^]別のアルゴリズムでは、バイナリヒープに対してΘ ( n )時間。^[⁷^]

[bootstrap-meld-10] 永続ヒープ（ decrece-keyをサポートしない）の場合、一般的な変換により、 meldのコストが挿入のコストまで削減されます。delete -minの新しいコストは、 delete-minとmeldの古いコストの合計になります。^[¹⁰^]ここで、meldはΘ (1)時間（挿入のコストが償却される場合）で実行されますが、 delete-minは依然としてO (log n )で実行されます。これを歪んだ二項ヒープに適用すると、最悪のケースの複雑さが最適な永続ヒープであるBrodal-Okasakiキューが生成されます。^[⁹^]

[pairingdecreasekey-17] [¹³^]の下限値^[¹⁴^]の上限値 $\Omega (\log \log n),$ $O(2^{2{\sqrt {\log \log n}}}).$

[optimum-21] Brodalキューと厳密なフィボナッチヒープは、ヒープの最悪ケース計算量を最適化する。これらは当初、命令型データ構造として記述された。Brodal-Okasakiキューは、減少キーがサポートされていないことを除いて、同様の最適化を実現する永続的データ構造である。

[Brodal-1] Gerth Stølting Brodal (1996). 最悪ケースにおける効率的な優先キュー. 第7回ACM-SIAM離散アルゴリズムシンポジウム講演論文集, pp. 52–58

[BrodalOkasaki-2] Gerth Stølting BrodalとChris Okasaki (1996).最適な純粋機能的優先キュー. Journal of Functional Programming.

[:0-3] Brodal, Gerth Stølting (1996). 「最悪ケースの効率的な優先キュー」(PDF) .{{cite web}}: CS1 maint: url-status (link)

[CLRS-4] コーメン、トーマス H. ;チャールズ・E・ライザーソン;リベスト、ロナルド L. (1990)。アルゴリズム入門(第 1 版)。 MIT プレスとマグロウヒル。ISBN 0-262-03141-8。

[sleator-tarjan-skew-5] 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 .

[tarjan-leftist-6] Tarjan, Robert (1983). 「3.3. 左派ヒープ」.データ構造とネットワークアルゴリズム. pp. 38– 42. doi : 10.1137/1.9781611970265 . ISBN 978-0-89871-187-5。

[hayward-mcdiarmid-heap-build-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日閲覧。

[9] 「二項式ヒープ | Brilliant Math & Science Wiki」brilliant.org . 2019年9月30日閲覧。

[brodal-okasaki-11] Brodal, Gerth Stølting; Okasaki, Chris (1996年11月)、「最適な純粋機能的優先度キュー」、Journal of Functional Programming、6 (6): 839– 857、doi : 10.1017/s095679680000201x

[12] Okasaki, Chris (1998). 「10.2. 構造的抽象化」.純粋関数型データ構造（第1版）. pp. 158– 162. ISBN 9780521631242。

[13] 高岡忠雄(1999) 「2-3ヒープ理論」 (PDF)、p.12

[Iacono-14] 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

[Fredman1999-15] Fredman, Michael Lawrence (1999年7月). 「ペアリングヒープと関連データ構造の効率について」(PDF) . Journal of the Association for Computing Machinery . 46 (4): 473– 501. doi : 10.1145/320211.320214 .

[16] ペティ, セス (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。

[18] ハウプラー、ベルンハルト;セン、シッダールタ。タージャン、ロバート E. (2011 年 11 月)。「ランクペアリングヒープ」(PDF)。サイアム J. コンピューティング。40 (6): 1463 ～ 1485 年。土井: 10.1137/100785351。

[Fredman_And_Tarjan-19] 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 .

[20] 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。

[22] Brodal, Gerth S. (1996)、「最悪ケースの効率的な優先キュー」（PDF）、第7回ACM-SIAM離散アルゴリズムシンポジウム論文集、pp. 52– 58

[23] Goodrich, Michael T. ; Tamassia, Roberto (2004). 「7.3.6. ボトムアップヒープ構築」. 『Javaにおけるデータ構造とアルゴリズム』（第3版）. pp. 338– 341. ISBN 0-471-46983-1。

[24] “オーフス大学のガース・シュトルティング・ブローダルのウェブサイト” . 2016 年2 月 18 日に取得。

[

[ 2 ]

[ 3 ]

[ 4 ]

[ a ]

[ 5 ]

[ 6 ]

[ 8 ]

[ b ]

[ 9 ]

[ 11 ]

[ 12 ]

[ c ]

[ 15 ]

[ 16 ]

[ 17 ]

[ d ]

[ 18 ]

[ 19 ]

[

[

[

[

[