バイナリヒープでの削除

Question

バイナリヒープを学び、バイナリヒープでの削除操作に関する疑問を抱いています。 私は、バイナリヒープから要素を削除することができると我々はそれをreheapifyする必要があることを読んだ。

しかし、次のリンクでは、それが使用できないと言う：

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 

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

ご説明いただきありがとうございます。

Answer 1

バイナリヒープとその他の優先度キュー構造は、通常、一般的な "要素削除"操作をサポートしません。ヒープ内の各要素のインデックスを追跡する追加のデータ構造が必要です。ハッシュテーブルあなたがいることを持っている場合は、最小値未満にハッシュテーブル

decrease keyと（1）予想時間

• 検索-要素、Oなどの一般的な削除操作を実装することができ、O（LG N）
• delete-minハッシュテーブルO（lg n）の予想時間を組み合わせて更新します。

Answer 2

DeleteMin/Maxと同様に通常の削除が可能です。 「問題」は、アップシフトとダウンシフトの両方をチェックしなければならないということです（つまり、「最後の」ノードが空き地を占めると、過大評価または過小評価される可能性があります）。あなたがO（lg n）で要素を見つけることができると述べていますが、私は方法を知らないでしょう。私の実装では、私は一般に、要素ではなくポインタから要素へのヒープを構築します（アップ/ダウンシフト中のより安価なコピー）。要素タイプに「位置」変数を追加し、要素のポインタのヒープ内のインデックスを追跡します。要素Eを指定すると、一定時間内にヒープ内の位置を見つけることができます。

明らかに、これはすべての実装。

Answer 3

質問のリンクでバイナリヒープの削除操作が利用できないと記載されているのは混乱します。バイナリヒープの削除はかなり可能で、バイナリヒープの2つの他の操作の構成です。 https://en.wikipedia.org/wiki/Binary_heap

私はあなたがバイナリヒープからキーを削除するバイナリヒープ

の他のすべての操作を知って検討していますコード/操作の2行が必要です。インデックスxのアイテムを削除するとします。可能な最小整数に値を減らしてください。それはInteger.MIN_VALUEです。 decreaseItem(int index, int newVal)の実行が完了すると、すべての整数の最小値なので、ルート位置に移動します。その後、extractMin()メソッドを呼び出すルートを抽出します。

// Complexity: O(lg n) 
public void deleteItem(int index) { 
    // Assign lowest value possible so that it will reach to root 
    decreaseItem(index, Integer.MIN_VALUE); 
    // Then extract min will remove that item from heap tree. correct ? 
    extractMin(); 
} 

全コード：BinaryHeap_Demo.java