基数ヒープ

基数ヒープは、単調な優先キューの操作を実現するためのデータ構造です。キーが割り当てられた要素のセットを管理できます。操作の実行時間は、最大のキーまたは定数と最小のキーまたは定数の差によって異なります。データ構造は主に、サイズが指数関数的に増加する一連のバケットで構成されます。

1. すべてのキーは自然数です。
2. 定数 C の場合の最大キー - 最小キーC。${\displaystyle \leq}$
3. extract -min操作は単調です。つまり、連続するextract-min呼び出しによって返される値は単調に増加します。

最も重要な 3 つのフィールドは次のとおりです。

1. ${\displaystyle b}$サイズ、最小インデックスが 0 のバケットを格納します。${\displaystyle B:=\lfloor log(C+1)\rfloor +1}$
2. ${\displaystyle u}$サイズ、最小インデックス 0 で、バケットの (下限) 境界を格納します。${\displaystyle B+1}$
3. ${\displaystyle bNum}$ヒープ内の各要素について、それが格納されているバケットを保持します。${\displaystyle x}$

上の図はデータ構造を示しています。次の不変条件が適用されます。

1. ${\displaystyle u[i]\leq }$キー入力: キー入力は、入力された値の範囲内で上下に移動する、または制限されます。${\displaystyle b[i]<u[i+1]}$${\displaystyle b[i]}$${\displaystyle u[i+1]}$${\displaystyle u[i]}$
2. ${\displaystyle u[0]=0,u[1]=u[0]+1,u[B]=\infty }$およびの場合: バケットのサイズは指数関数的に増加します。${\displaystyle 0\leq u[i+1]-u[i]\leq 2^{i-1}}$${\displaystyle i=1,\ldots ,B-1}$

制限の指数関数的増加 (したがってバケットが保持する範囲) に注意することが重要です。このように、フィールド量の対数依存性は、2 つのキー値の最大差である値 C になります。

初期化中に、空のバケットが生成され、下限が生成されます（不変式 2 に従って）。実行時間。 ${\displaystyle u}$${\displaystyle O(B)}$

挿入中、新しい要素はバケットを介して右から左に直線的に移動され、実行時間とともに新しい要素が左側のバケットに格納されます。 ${\displaystyle x}$${\displaystyle k(x)}$${\displaystyle u[i]\geq k(x)}$${\displaystyle O(B)}$

decline-keyの場合、最初にキー値が減らされます (不変条件への準拠をチェック)。次に、フィールドを使用して要素を検索し、必要に応じて挿入操作と同様に左に反復します。実行時間は(償却) です。 ${\displaystyle bNum}$${\displaystyle O(1)}$

extract-min操作は、バケットから要素を削除して返します。バケットがまだ空でない場合、操作は終了します。ただし、バケットが空の場合は、次に大きい空でないバケットが検索され、その最小の要素が追跡されてk に設定されます (これには単調性が必要です)。次に、不変条件に従って、バケットの境界が再定義され、要素が新しく形成されたバケットに削除されます。実行時間(償却)。 ${\displaystyle b[0]}$${\displaystyle b[0]}$${\displaystyle k}$${\displaystyle u[0]}$${\displaystyle b[i]}$${\displaystyle O(1)}$

表示されている場合、フィールドが更新されます。 ${\displaystyle bNum}$

• BV Cherkassky、AV Goldberg、C. Silverstein: バケット、ヒープ、リスト、およびモノトーン優先キュー (要約)、第 8 回 ACM-SIAM 離散アルゴリズムシンポジウムの議事録。1997 年 1 月、83 ～ 92 ページ。