プログラミング
 Computer >> コンピューター >  >> プログラミング >> プログラミング

溶融可能なDEPQ

  • メルダブルDEPQ（MDEPQ）は、上記のDEPQ操作に加えて、操作meld（p、q）...を含むDEPQ（Double Ended Priority Queue）として定義されます。単一のDEPQ。ダブルエンド優先キューpとqをマージした結果は、pとqのすべての要素を含む単一のダブルエンド優先キューになります。メルド操作は、メルドに続いて、pとqが独立したDEPQとして残っていないという点で破壊的です。
  • 2つのDEPQを線形時間未満でマージするには、DEPQを、（ヒープの配列表現のような暗黙的なポインターではなく）明示的なポインターを実装して表現する必要があります。最初の場所から最後の場所まで。
  • 最小-最大ペアヒープがこのように表される場合、要素（サイズn）DEPQが別の要素（サイズk）（ここでk <=n）とOで融合される可能性があることを示すことができます。 （log（n / k）* log k）時間。
  • サイズaとbの2つの最小-最大ヒープをそれぞれマージする複雑さはΩ（a + b）であることを示すことができます。
  • 最小要素と最大要素を計算し、要素を挿入し、O（1）時間で2つの優先キューをマージできるようにするMDEPQ実装。最小要素または最大要素を削除するのに必要な時間はO（log n）です。
  • 左翼ツリーは、メルドが対数時間を消費し、残りの操作が前述のDEPQ表現のいずれかが実装されている場合と同じ漸近的な複雑さを持つMDEPQの単純な表現を取得するように適合できることを示すことができます。
  • ベースMPQ構造としてのFMPQ（Fast Meldable Priority Queue）構造を実装すると、removeMaxとremoveMinが対数時間を消費し、残りの操作が一定を消費する、完全対応のMDEPQ構造が得られることに注意してください。時間。スペース要件がほぼ半分であるため、このアダプテーションは、デュアルプライオリティキューアダプテーションと比較して優れています。さらに、全体的な対応の適応は、二重優先キューの適応よりも高速です。

  1. デュアルプライオリティキュー

    remove（bNode）操作の効率的な実装も提供するシングルエンド優先キュー（PQ）データ構造から効率的なDEPQ（Double Ended Priority Queue）データ構造に到達するための一般的な方法の存在（この操作はノードbNodeをPQ）。これらの最も単純な方法である二重構造法は、同じ要素を構成する最小PQと最大PQのノード間の対応ポインターに関連付けられたすべてのDEPQ要素の最小PQと最大PQの両方を維持します。 図Dは、要素7、8、3、6、5のデュアルヒープ構造を示しています。対応ポインターは赤い矢印で表示されます。 図D：デュアルヒープ この図は、最小ヒープ

  2. DEPQのジェネリックメソッド

    デュアルヒープ remove（aNode）操作の効率的な実装も提供するシングルエンド優先キュー（PQ）データ構造から効率的なDEPQ（ダブルエンド優先キュー）データ構造に到達するための一般的な方法の存在（この操作はノードaNodeをPQ）。これらの方法の中で最も単純な二重構造法は、同じ要素を構成する最小PQと最大PQのノード間の対応ポインターに関連付けられたすべてのDEPQ要素の最小PQと最大PQの両方を追跡します。 図Aは、要素7、8、3、6、5のデュアルヒープ構造を示しています。対応ポインターは赤い矢印で表示されます。 図A：デュアルヒープ この図は、最小ヒープと最大ヒープの