2～3山

コンピュータサイエンスにおいて、2-3ヒープは、優先度付きキューを実装するデータ構造です。これは、1999年に高岡忠雄によって設計されたヒープの一種です。この構造はフィボナッチヒープに似ており、 2-3ツリーから着想を得ています。

一般的なヒープ操作に必要な時間は次のとおりです。

• Delete-minには償却時間がかかり、最悪の場合.${\displaystyle O(\log(n))}$
• 減少キーには一定の償却時間がかかります。
• 最悪の場合、挿入には一定の償却時間と時間がかかります。${\displaystyle O(\log(n))}$

木の多項式

出典: ^{[ 1 ]}

サイズ の線形木は、最初のノードを木の根とするノードの連続パスであり、太字で表されます（例：は単一ノードの線形木です）。2つの木 と の積は、 のすべてのノードを のコピーに置き換えることで生成される木です。 の各辺に対して、 の端点を置き換えた木の根を結ぶ辺が に存在します。この積の定義は結合的ですが、可換ではありません。2つの木 と の和は、2つの木 との森です。 ${\displaystyle r}$ ${\displaystyle r}$ ${\displaystyle \mathbf {r} }$ ${\displaystyle \mathbf {1} }$ ${\displaystyle P=ST}$ ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle S}$ ${\displaystyle ST}$ ${\displaystyle S+T}$ ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle S}$ ${\displaystyle T}$

木に対する演算は以下のように定義されます。木は、木の根を木 の根の子として連結することで生成されます。ここで線形木 を考えてみましょう。木は、のr個のコピーを以下のように 結合することで定義されます。${\displaystyle \triangleleft}$ ${\displaystyle S,T}$ ${\displaystyle L=S\triangleleft T}$ ${\displaystyle T}$ ${\displaystyle S}$ ${\displaystyle \mathbf {r} }$ ${\displaystyle \mathbf {r} ^{i}}$ ${\displaystyle \mathbf {r} ^{i-1}}$

${\displaystyle \mathbf {r} ^{i}=\mathbf {r} ^{i-1}\triangleleft \mathbf {r} ^{i-1}\triangleleft \dots \triangleleft \mathbf {r} ^{i-1}}$ (右から左に評価されます)。

このリンクから作成されたパスは、ツリーの 番目の次元 とも呼ばれる 番目のトランクを形成します。${\displaystyle i}$ ${\displaystyle \mathbf {r} ^{i}}$ ${\displaystyle i}$

木のr元多項式は、 と定義されます。このノードの木の多項式表記は一意です。木は、 のコピーで構成され、それらの根は順に辺で接続されます。これらの辺の経路は、木の主幹と呼ばれます。さらに、木のr元多項式のノードがヒープ特性 を満たすキーに関連付けられている場合、木のr元多項式はr項キューと呼ばれます。 ${\displaystyle P=\mathbf {a} _{k-1}\mathbf {r} ^{k-1}+\dots +\mathbf {a} _{1}\mathbf {r} +\mathbf {a} _{0}}$ ${\displaystyle 0\leq a_{i}\leq r-1}$ ${\displaystyle n}$ ${\displaystyle \mathbf {a} _{i}\mathbf {r} ^{i}}$ ${\displaystyle a_{i}}$ ${\displaystyle \mathbf {r} ^{i}}$ ${\displaystyle a_{i}-1}$ ${\displaystyle a_{i}-1}$ ${\displaystyle \mathbf {a} _{i}\mathbf {r} ^{i}}$

多項式ヒープ、実際には木の次元表現を持つ(2,3)ヒープ

r項キューの操作

と の2つの項をマージするには、ツリーのルートのキーに基づいて、ツリーを主幹内で並べ替えます。 の場合、の項とキャリーツリーが存在します。それ以外の場合は、ツリー のみとなります。2つのr項キューの和は、 を底とする2つの数の加算に似ています。 ${\displaystyle \mathbf {a} _{i}\mathbf {r} ^{i}}$ ${\displaystyle \mathbf {a} '_{i}\mathbf {r} ^{i}}$ ${\displaystyle a_{i}+a'_{i}\geq r}$ ${\displaystyle (\mathbf {a} _{i}+\mathbf {a} '_{i}-\mathbf {r} )\mathbf {r} ^{i}}$ ${\displaystyle \mathbf {r} ^{i+1}}$ ${\displaystyle (\mathbf {a} _{i}+\mathbf {a} '_{i})\mathbf {r} ^{i}}$ ${\displaystyle r}$

多項式キューへのキーの挿入は、キーのラベルを持つ単一のノードを既存の r 項式キューにマージするようなものであり、時間がかかります。 ${\displaystyle O(r\log _{r}{n})}$

最小値の削除操作は、例えば木の根にある最小値を見つけて削除することで行われます。結果として得られる多項式キューは、合計時間 でに戻されます。 ${\displaystyle T}$ ${\displaystyle Q}$ ${\displaystyle PT}$ ${\displaystyle O(r\log _{r}{n})}$

(2,3)ヒープ

出典: ^{[ 1 ]}

木は再帰的に定義される ${\displaystyle (l,r)-}$ ${\displaystyle T(i)}$

${\displaystyle T(i)=\left\{{\begin{array}{cc}{\text{単一ノード}}&i=0\\T_{1}(i-1)\triangleleft \dots \triangleleft T_{s}(i-1)&i\geq 1{\text{ かつ }}l\leq s\leq r\end{array}}\right.}$

木の根は次数 で、次数 の異なる木によって形成されます。 の根は番目の幹のヘッドノードと呼ばれます。幹上の非ヘッドノードの次元は ですが、ヘッドノードの次元は、再リンクの有無に応じて またはそれ以上になります。 の 番目の幹上の、 ノードを根とする型の木はと呼ばれます。 ${\displaystyle T(i)}$ ${\displaystyle i}$ ${\displaystyle i-1}$ ${\displaystyle T(i)}$ ${\displaystyle i}$ ${\displaystyle i-1}$ ${\displaystyle i}$ ${\displaystyle T(i-1)}$ ${\displaystyle i}$ ${\displaystyle T(i)}$ ${\displaystyle v}$ ${\displaystyle 木(v)}$

非公式には、次元ツリーは、2 つまたは 3 つの次元ツリーのルートを1 行にリンクすることによって形成されます。 ${\displaystyle (2,3)}$ ${\displaystyle d}$ ${\displaystyle d-1}$

木の拡張多項式 はによって定義されます。${\displaystyle P}$ ${\displaystyle P=a_{k-1}T(k-1)+\dots +a_{1}T(1)+a_{0}}$

2-3ヒープの例。P = 2T(3) + 1T(2) + 1T(0)

ヒープ順序で拡張された木の多項式のノードにキーが割り当てられている場合、それは と呼ばれ、との特殊なケースは です。${\displaystyle (l,r)-ヒープ}$ ${\displaystyle l=2}$ ${\displaystyle r=3}$ ${\displaystyle (2,3)-ヒープ}$

ノード13（黄色）とノード22（青）のワークスペースと、ピンク色のノードの次元を示すラベル（2,3）のツリー

ノードのワークスペース ノードのワークスペースは、ヒープ内のツリーの主幹上にないノードに対して定義される局所近傍です。 の次元が で、これが番目の幹上にあると仮定します。この場合、 のワークスペースは、番目の幹上のすべてのノード、番目の幹上のノード、およびヘッドノードが番目の幹上にある他の 番目の幹上のノードで構成されます。この場合、ワークスペースはサイズが4から9までのノードの集合です。ワークスペースのヘッドノードは、 番目の幹の最初の位置にあるノードです。 ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle i-1}$ ${\displaystyle i}$ ${\displaystyle v}$ ${\displaystyle i}$ ${\displaystyle i+1}$ ${\displaystyle i}$ ${\displaystyle i+1}$ ${\displaystyle i+1}$

(2,3)ヒープ上の操作

挿入: 新しいキーを挿入するには、既存の(2,3)-ヒープを、このキーでラベル付けされた単一ノードツリーとマージします。拡張多項式では、挿入によって発生する可能性のあるツリーのキャリーを調整する必要がある場合があります。最上位レベルのツリーにツリーを挿入する場合、 の値に応じて3つのケースがあります。 ${\displaystyle T(0)}$ ${\displaystyle 0\leq a_{k}\leq r-1=2}$ ${\displaystyle T(i)}$ ${\displaystyle \mathbf {a} _{i}T(i)}$ ${\displaystyle \mathbf {a} _{i}}$

1. ${\displaystyle \mathbf {a} _{i}=0}$ :ヒープ内に既に木が存在しないため、これをヒープに挿入します。項は拡張多項式に追加されます。${\displaystyle T(i)}$ ${\displaystyle T(i)}$
2. ${\displaystyle \mathbf {a} _{i}=1}$ :ラベルのヒープ順序プロパティを維持するために、1 つの比較を使用して 2 つのツリーを結合し、新しいツリーを形成します。${\displaystyle \mathbf {2} T(i)}$
3. ${\displaystyle \mathbf {a} _{i}=2}$ : 2回の比較でキャリーが行われます。このキャリーツリーをヒープに保持したまま、次の挿入ラウンドが実行されます。${\displaystyle T(i+1)}$ ${\displaystyle \mathbf {a} _{i+1}T(i+1)}$

最小値削除: まず、木の根をスキャンして最小値を見つけます。最小値を含む木を とします。この木が存在するので、または であったことを意味します。この木の根を削除するということは、 のコピーを繋ぐ線形連鎖の根を削除することを意味します。 の他のコピーは、またはの場合にという形式の木を生成します。 ${\displaystyle \mathbf {a} _{i}T(i)}$ ${\displaystyle \mathbf {a} _{i}}$ ${\displaystyle \mathbf {1} }$ ${\displaystyle \mathbf {2} }$ ${\displaystyle \mathbf {a} _{i}}$ ${\displaystyle T(i)}$ ${\displaystyle T(i)}$ ${\displaystyle \mathbf {b} _{i}T(i)}$ ${\displaystyle \mathbf {b} _{i}=0}$ ${\displaystyle \mathbf {a} _{i}=1}$ ${\displaystyle \mathbf {b} _{i}=1}$ ${\displaystyle \mathbf {a} _{i}=2}$

削除されたルートは、 の最初のコピーのルートでもあったため、2つまたは3つのツリーが生成されます。このパターンに従うと、ツリーのコレクションが得られます。 ${\displaystyle T(i)}$ ${\displaystyle T(i-1)}$

${\displaystyle \mathbf {b} _{j}T(0),\mathbf {b} _{j}T(1),\dots ,\mathbf {b} _{j}T(i)}$

ここで、はまたはであり、は上記で指定したとおりです。 ${\displaystyle \mathbf {b} _{j}}$ ${\displaystyle \mathbf {1} }$ ${\displaystyle \mathbf {2} }$ ${\displaystyle j=0,\dots ,i-1}$ ${\displaystyle \mathbf {b_{i}} }$

このコレクションはヒープを形成し、その後、最小のノードのみがヒープから削除されたことを確認するために、マージし直すことができます。(マージ操作は複数の挿入を通じて行われ、各挿入では最大 3 回の比較が行われます)。 ${\displaystyle Q}$ ${\displaystyle P-\mathbf {a} _{i}T(i)}$

ツリーの削除：ヒープの最上位のトランクをルートとするツリーは削除されません。ノード型のツリーを削除するには、ワークスペースのサイズが4の場合と、それより大きい場合の2つのケースがあります。はヒープの 番目のトランク 上のノードであることに注意してください。${\displaystyle tree(v)}$ ${\displaystyle T(i-1)}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle i}$

ワークスペースのサイズが4より大きい場合、 番目のトランクには 2 個または 3 個のノードがあります。3 個のノードがある場合、またはの形式になります。いずれの場合も、トランクを削除して縮小します。は 番目のトランクの最初のノードにはならないことに注意してください。なぜなら、そのノードは番目のトランク上にある必要があるからです。最上位のトランクにあるノードは削除されません。 ${\displaystyle i}$ ${\displaystyle (u,v,w)}$ ${\displaystyle (u,w,v)}$ ${\displaystyle tree(v)}$ ${\displaystyle v}$ ${\displaystyle i}$ ${\displaystyle i+1}$

番目のトランクが の形式である場合は、 を削除し、ワークスペース内の タイプの他のいくつかのツリーを移動することによって、 番目のトランクの損失を考慮します。${\displaystyle i}$ ${\displaystyle (u,v)}$ ${\displaystyle tree(v)}$ ${\displaystyle i}$ ${\displaystyle T(i-1)}$

ワークスペースのサイズが4の場合、残りの3つのノードを削除して再配置し、2つがワークスペースのヘッドノードの下に来るようにします。これにより、長さ2の th のトランク（3つのノードが一列に並ぶ）が作成されますが、th のトランクが失われます。この損失は、 th 次元のノードのワークスペースからツリーを移動することで修正されます。このプロセスは、問題が解決されるまで次元の上方へと続けられます。 ${\displaystyle tree(v)}$ ${\displaystyle i}$ ${\displaystyle (i+1)}$ ${\displaystyle (i+1)}$

減少キー：次元のノードのキーが減少し、それが最上位レベルではないと仮定します。その後、 が削除され、ヒープの最上位レベル（つまり拡張多項式内）の 番目の項に挿入されます。ここで がツリーの最上位レベルにあった場合、減少キーによるヒープ特性は破られておらず、ツリーの削除は不要です。ただし、最上位のトランクのトランクの再配置が必要になる場合があります。 ${\displaystyle v}$ ${\displaystyle i-1}$ ${\displaystyle tree(v)}$ ${\displaystyle j}$ ${\displaystyle T(j)}$ ${\displaystyle j=dim(v)}$ ${\displaystyle v}$ ${\displaystyle i}$

業務分析

ポテンシャル法は、操作実行にかかる償却時間を分析するために使用できます。3つのノードからなるトランクのポテンシャルを3、2つのノードからなるトランクのポテンシャルを1とします。関数をすべてのトランクのポテンシャルの合計として定義し、 とします。実際のコストは、操作中に実行される比較の回数になります。空のヒープのポテンシャルは0であることに注意してください。 ${\displaystyle S}$ ${\displaystyle \phi =-S}$

減少キー ツリーの削除中に、ワークスペースのサイズに応じて、幹上のノードの数が増減することがあります。それぞれのケースで、潜在的な比較数とノード数の変化を観察できるため、償却コストを計算することができます。

左下に向かう幹は、そのうちの1つが立っている次元とします。右下に向かう幹は次元とします。これらの幹は、実際には先頭ノードのラベルで順序付けられますが、長さが減少する順序で並べられています。 ${\displaystyle i}$ ${\displaystyle v}$ ${\displaystyle i+1}$ ${\displaystyle i}$

異なるワークスペースサイズでの削除事例。削除前（左）と削除後（右）。緑色のノードは削除の対象となる可能性のあるオプションです。

の場合、および のケース 1 の場合、ヒープ特性と のため比較は不要です。これらの場合の償却コストは です。 ${\displaystyle w=9,8,5}$ ${\displaystyle w=7}$ ${\displaystyle \Delta \phi =-\Delta S=-(-2)}$ ${\displaystyle {\hat {c_{i}}}=0+\Delta \phi =2}$

のケース 1および の両方のケースでは、最大で 1 回の比較が必要となり、が 1 減少して償却コストが 1 になります。 ${\displaystyle w=7}$ ${\displaystyle w=6}$ ${\displaystyle \Delta S}$

最後のケース（ ）では、最大で1回の比較が行われ、が1増加し、償却コストは0になります。番目のトランクの損失は、トランクから削除される前に、ノードの上位ワークスペースを使用して修正する必要があります。修正プロセスは、前述のいずれかのケース、または上位トランクが存在しない場合のいずれかで終了します。償却コストは非負であり、このプロセスでは償却コストが正となるケースのうち1つのみが実行されるため、全体の償却コストは一定のままです。 ${\displaystyle w=4}$ ${\displaystyle \Delta S}$ ${\displaystyle i+1}$

挿入ツリー内の既存のノードに単一のノードを挿入する場合、 と の比較が2回発生するか、との比較が1回発生します。したがって、最初の挿入から繰り越しまで、償却コストは0です。実際の最悪ケースの時間は、繰り越しと毎回の一定数の比較によって発生します。 ${\displaystyle \mathbf {a} _{0}T(0)}$ ${\displaystyle \Delta S=2}$ ${\displaystyle \mathbf {a} _{0}=2}$ ${\displaystyle \Delta S=1}$ ${\displaystyle O(\log n)}$

最小値を削除最小要素を見つけるのに時間がかかります。また、小さなサブツリーは最大で数個あるため、それらを分割するのにも時間がかかります。サブツリーを結合するために挿入が行われますが、それぞれの挿入には一定の償却時間がかかります。償却時間は であり、最悪のケースの時間は です。 ${\displaystyle O(\log n)}$ ${\displaystyle O(\log n)}$ ${\displaystyle O(\log n)}$ ${\displaystyle O(\log n)}$ ${\displaystyle O(\log n)}$

参考文献

1. 高岡忠夫 (2003年3月). 「2–3ヒープ理論」 .離散応用数学. 126 (1): 115– 128. doi : 10.1016/S0166-218X(02)00219-6 .