デザイン最小/最大優先度キュー

-1

最小/最大優先度キューを挿入して削除し、最小値を削除する必要があります（すべて対数時間）。と最大値を見つけ、最小値を見つける（両方とも一定時間内に）。デザイン最小/最大優先度キュー

2017-07-29 John Wick

あなたは、通常の最大ヒープを設計する方法について熟知していますか？ DSを実装するために1つ（または2つ）を使用できると思いますか？ – amit

はい私は最大のヒープを設計することに慣れています。 –

これに2つのヒープを使用できますか？ –

方法1：amitとして

、2つのヒープを維持し、要素へのポインタを覚えて、議論を通じてあなたを導きます。

方法2：（良い）

この目的のための具体的データ構造があります。その名前はMin-Max Heapです。同様に、同じ仕様のMax-Minヒープもあります。あなたが望むものに基づいている

仕様：

1）挿入 - O（LOGN）

2）DeleteMin - O（LOGN）

3）DeleteMax - O（LOGN ）

4）作成 - O（n）を

5）FindMin - O（1）

6）FindMax - O（1）

いくつかの参考文献：

Min-Max Heap

2017-07-29 17:40:04 Suparshva

答えて