6

バイナリヒープを学習しようとしていますが、バイナリヒープで削除操作を実行することに疑問があります。バイナリヒープから要素を削除できるので、それを再ヒープ化する必要があることを読みました。

しかし、次のリンクでは、利用不可と表示されています。

http://en.wikibooks.org/wiki/Data_Structures/Tradeoffs

                Binary Search  AVL Tree   Binary Heap (min)  Binomial Queue (min)

Find            O(log n)       O(log n)   unavailable         unavailable
Delete element  O(log n        O(log n)   unavailable         unavailable

私はそれについて少し混乱しています。

すべての説明を事前に感謝します。

4

3 に答える 3

3

バイナリ ヒープやその他の優先キュー構造は、通常、一般的な "要素の削除" 操作をサポートしていません。ハッシュテーブルなど、ヒープ内の各要素のインデックスを追跡する追加のデータ構造が必要です。それがある場合は、一般的な削除操作を次のように実装できます。

  • find-element、O(1) ハッシュ テーブルでの予想時間
  • キーを最小値よりも小さくします。O(lg n ) 時間
  • delete-min とハッシュ テーブルの更新、O(lg n ) を組み合わせた予想時間。
于 2011-09-28T12:02:53.470 に答える
2

DeleteMin/Max と同様に、通常の削除が可能です。「問題」は、アップシフトとダウンシフトの両方をチェックする必要があることです (つまり、「最後の」ノードが空いている場所を占めると、過大評価または過小評価される可能性があります。まだ両方になることはできないため、明らかです)正当性をチェックするのは簡単です。

残っている唯一の問題は検索です。上記の答えは、O(lg n) で要素を検索できると述べていますが、その方法はわかりません。私の実装では、通常、要素ではなく要素へのポインターのヒープを構築します (アップ/ダウンシフト中のコピーが安価です)。ヒープ内の要素のポインターのインデックスを追跡する「位置」変数を要素型に追加します。このようにして、要素 E が与えられると、一定時間でヒープ内の位置を見つけることができます。

明らかに、これはすべての実装に適しているわけではありません。

于 2012-03-27T09:37:53.177 に答える