クイープ

コンピュータサイエンスにおいて、キューは優先度付きキューデータ構造の一種です。このデータ構造では、任意の要素の挿入と削除、および最優先度要素の取得が可能です。削除には、削除対象の要素よりも長く構造内に存在していた要素の数の対数に比例する償却時間が必要です。挿入には一定の償却時間が必要です。

このデータ構造は、二重リンクリストと2-4ツリーデータ構造から構成され、それぞれが最小優先度要素を追跡するように変更されています。この構造の基本的な操作は、削除によってリスト項目のいずれかが削除されるまで、新しく挿入された要素を二重リンクリストに保持し、削除された時点でそれらすべてを2-4ツリーに移動することです。2-4ツリーは、より一般的な優先度順ではなく、挿入順に要素を格納します。

データ構造とその名称は、ジョン・イアコノとステファン・ランガーマンによって考案された。^{[ 1 ]}

queap は、要素の挿入を償却時間O (1) で行い、抽出する要素よりも長くヒープ内に存在する項目がk個ある場合は最小の要素をO (log( k  + 2)) で削除する優先度付きキューです。queap には、queuish プロパティと呼ばれる特性があります。要素xの検索時間は O(lg q ( x ))で、 q ( x ) はn − 1 − w ( x )に等しく、 w ( x ) は検索、挿入、削除などの操作によってアクセスされた異なる項目の数です。q ( x ) は、xの最後のアクセス以降にアクセスされていない要素の数として定義されます。実際、queuish プロパティは、splay ツリーのワーキング セット プロパティの補集合です。要素xの検索時間はO (lg w ( x ))です。     

クイープは、二重リンクリストと修正版2-4ツリーという2つのデータ構造で表現できます。二重リンクリストLは、挿入と最小値探索操作の一連の操作に使用されます。クイープは、リストに格納されている最小要素へのポインタを保持します。要素xをリストlに追加するには、要素xをリストの末尾に追加し、要素x内のビット変数を1に設定します。この操作は、要素がリスト内にあるか、2-4ツリー内にあるかを判定するために行われます。

削除操作が発生すると、2-4ツリーが使用されます。項目xが既にツリーTに存在する場合、2-4ツリー削除操作を使用して項目が削除されます。そうでない場合、項目xはリストLに存在します（ビット変数が設定されているかどうかを確認します）。次に、リストLに格納されているすべての要素が2-4ツリーに追加され、各要素のビット変数がゼロに設定されます。その後、 xはTから削除されます。

queap は、探索木ではなく、2-4 ツリー構造の特性のみを使用します。修正された 2-4 ツリー構造は次のとおりです。リストLが次の要素セットを持っているとします。${\displaystyle x_{1},x_{2},x_{3},\dots ,x_{k}}$削除操作が呼び出されると、Lに格納されている要素のセットが、無限キーを含むダミーの葉に続いて、2-4ツリーの葉にその順序で追加されます。Tの各内部ノードにはポインタがあります。${\displaystyle h_{v}}$は、サブツリーv内の最小の項目を指します。ルートからパスP上の各内部ノードは、${\displaystyle x_{0}}$ポインターを持つ${\displaystyle c_{v}}$これは、${\displaystyle T-T_{v}-\{r\}}$.${\displaystyle h_{v}}$パスP上の各内部ノードのポインタは無視されます。queap には、${\displaystyle c_{x_{0}}}$これは、 Tの最小要素を指し示しています。

queapsの応用例としては、優先度の高いイベントの固有のセットと、処理対象として最も優先度の高いイベントの抽出が挙げられる。

minL を二重リンクリストL内の最小要素を指すポインタとする。${\displaystyle c_{x_{0}}}$は2-4ツリーTに格納されている最小要素、kはTに格納されている要素の数、nはqueap Qに格納されている要素の総数とする。操作は以下のとおりである。

New(Q):新しい空のキュープを初期化します。

空の二重リンクリストLと2-4ツリーTを初期化します。kとnをゼロに設定します。

Insert(Q, x):要素xを queap Qに追加します。

要素xをリストLに挿入します。要素xのビットを1 に設定して、要素がリストLに含まれていることを示します。xがリスト内の最小要素である場合は、minLポインタを更新します。nを 1 増やします。

Minimum(Q): queap Qから最小要素へのポインタを取得します。

key (minL) < key (${\displaystyle c_{x_{0}}}$)、minLを返します。それ以外の場合は、${\displaystyle c_{x_{0}}}$。

Delete(Q, x): queap Qから要素 x を削除します。

要素xのビットが 1 に設定されている場合、その要素はリストLに格納されます。L のすべての要素を T に追加し、各要素のビットを 0 に設定します。各要素は、 2-4 ツリーの挿入操作を使用して、Tの最も右の子の親に追加されます。Lは空になります。更新${\displaystyle h_{v}}$子ノードが新規または変更されたすべてのノードvへのポインタを取得し、親ノードがルートノードと等しくなるまで次の親ノードでこのプロセスを繰り返します。ルートからノードまで移動します。 ${\displaystyle x_{0}}$、そして更新します${\displaystyle c_{v}}$値。kをnと等しく設定します。

要素xのビットがゼロに設定されている場合、xはTの葉です。2-4 ツリー削除操作を使用して x を削除します。ノードxから開始して、Tをノードまで移動します。${\displaystyle x_{0}}$更新中${\displaystyle h_{v}}$そして${\displaystyle c_{v}}$ポインタ。nとkを1減らします。

DeleteMin(Q): queap Qから最小の要素を削除して返します。

Minimum(Q)操作を呼び出します。この操作はminを返します。Delete (Q, min)操作を呼び出します。min を返します。

CleanUp(Q):リストLとツリーTのすべての要素を削除します。

リストLの最初の要素から始めて、リストを走査し、各ノードを削除します。

ツリーTの根から始めて、後順走査アルゴリズムを使用してツリーを走査し、ツリー内の各ノードを削除します。

実行時間は償却分析を用いて分析される。queap Q のポテンシャル関数は次のようになる。${\displaystyle \phi (Q)=c|L|}$どこ${\displaystyle Q=(T,L)}$。

Insert(Q, x):操作のコストはO(1)です。リストLのサイズが1 増え、ポテンシャルが定数cだけ増加します。

最小値(Q):この操作はデータ構造を変更しないため、償却コストは実際のコストと等しくなり、O(1)となります。

Delete(Q, x): 2 つのケースがあります。

queapの簡単なJava実装：

public class Queap { public int n , k ; public List < Element > l ; // Element は汎用データ型です。public QueapTree t ; // Queap 用に修正された 2-4 ツリーpublic Element minL ;private Queap ( ) { n = 0 ; k = 0 ; l = new LinkedList <Element> ( ); t = new QueapTree (); }public static Queap New () { return new Queap (); }public static void Insert ( Queap Q , Element x ) { if ( Q.n == 0 ) Q.minL = x ; Q.l.add ( x ) ; x.inList = true ; if ( x.compareTo ( Q.minL ) < 0 ) Q.minL = x ; }​​​​​​​​​​​​​​​public static Element Minimum ( Queap Q ) { // t は 2-4 ツリーで、x0、cv はツリーノードです。if ( Q . minL . compareTo ( Q . t . x0 . cv . key ) < 0 ) return Q . minL ;return Q.t.x0.cv.key ; }​​​​​​​​public static void Delete ( Queap Q , QueapNode x ) { Q.t.deleteLeaf ( x ) ; --Q.n ; --Q.k ; }​​​​​​​​​public static void Delete ( Queap Q , Element x ) { QueapNode n ; if ( x.inList ) { //リスト内のすべての要素のinListをfalseに設定n = Q.t.insertList ( Q.l , x ) ; Q.k = Q.n ; Delete ( Q , n ) ; } else if ( ( n = Q.t.x0.cv ) .key == x ) Delete ( Q , n ) ; }​​public static Element DeleteMin ( Queap Q ) { Element min = Minimum ( Q ); Delete ( Q , min ); return min ; } }

• キュー（データ構造）
• 枝分かれした木