4

したがって、バイナリ ヒープで実装されたプライオリティ キューを使用して、プライオリティを持つ N 個のアイテムのプライオリティ キューがあるとします。ここで、N は数千の単位です。EXTRACT-MINとのINSERTプリミティブを理解しています ( ではなくを使用するCormen、Leiserson、Rivestを参照)。-MAX-MIN

しかしDELETE、DECREASE-KEY両方とも、アイテム自体が与えられたヒープ内のアイテムのインデックスを見つけることができるように優先度キューを必要とするようです (または、そのインデックスは優先度キューの消費者によって与えられる必要がありますが、これは抽象化違反のようです)。 .. 見落としのようです。ヒープの上にハッシュテーブルを追加することなく、これを効率的に行う方法はありますか?

4

6 に答える 6

1

FWIW、そして誰かがまだ似たようなものを探している場合 — 最近、アルゴリズムに関する Coursera コースの 1 つを行っているときに、インデックス付き優先キューの実装を偶然見つけました。

基本的な要点は、OPが述べた操作をサポートするために、2つの配列を使用して逆引きを組み込むことです。

Min Ordered Indexed Priority Queueの明確な実装を次に示します。

于 2013-04-09T13:33:02.927 に答える
1

そうです、ここでのポイントは、プライオリティ キューの実装のために、API のバイナリ ヒープを使用して、その HEAP-INCREASE-KEY(A, i, key) のインデックス (i) を使用できるということだと思いますが、プライオリティ キューは、任意のキーを取得できます。key->index マップの詳細をカプセル化するプライオリティ キューを自由に作成できます。PQ-INCREASE-KEY(A, old, new) を O(log n) で動作させる必要がある場合は、O(log n) またはインデックス ルックアップのキーを最新の状態に保つことをお勧めします。これは、ハッシュ テーブルまたはその他の高速検索構造である可能性があります。

ですから、あなたの質問に答えるには、データ構造が何らかの方法で拡張されることは避けられないと思います。

于 2009-09-24T09:06:08.607 に答える
0

ただし、DELETEとDECREASE-KEYはどちらも、アイテム自体が指定されたヒープ内でアイテムのインデックスを検索できるようにするために、優先度付きキューを必要とするようです。

実際、それは真実ではありません。これらの操作は、先行ポインタと後続ポインタを使用することで、インデックス付けされていないグラフ、リンクリスト、および「従来の」検索ツリーに実装できます。

于 2013-01-05T09:43:58.077 に答える
0

ノード クラスを変更して、heapIndex メンバーを追加しました。これは、挿入、削除、減少などの際にノードがスワップされるため、ヒープによって維持されます。

これはカプセル化を破ります (私のノードは現在ヒープに結び付けられています) が、私の状況ではより重要だった高速に実行されます。

于 2010-02-08T05:21:38.150 に答える
0

1 つの方法は、ヒープを一方の要素と他方の組織に分割することです。

完全な機能を実現するには、2 つのリレーションが必要です。b) 要素を指定して、そのヒープの場所を見つけます。

2 つ目は非常に簡単です。要素がヒープ内で移動するたびに更新される値の「場所」 (配列ベースのヒープ内のインデックスである可能性が最も高い) を追加します。

1 つ目も単純です。Elements を格納する代わりに、Elements (または配列インデックス) へのポインターのヒープを保持するだけです。ここで、場所 (例: ルート) を指定すると、参照解除 (またはベクトルへのアクセス) によってそこに配置されている要素を見つけることができます。

于 2012-08-23T15:24:29.623 に答える
0

「しかし、DELETE と DECREASE-KEY はどちらも、アイテム自体が与えられたヒープ内のアイテムのインデックスを見つけることができるようにするために、プライオリティ キューを必要とするようです」 -- コードから、これらのメソッドの少なくともいくつかがインデックスを使用してアイテムの優先度ではなくヒープ。明らかに、i は HEAP-INCREASE-KEY のインデックスです。

HEAP-INCREASE-KEY(A, i, key)
    if key < A[i]
        then error 'new key is smaller than current key"
    A[i] <-- key
    ...

それがAPIであれば、それを使用してください。

于 2009-08-17T23:21:35.843 に答える