在二進制堆中刪除

我只是想學習二進制堆，並且對在二進制堆中執行刪除操作有疑問。我讀過，我們可以從二進制堆中刪除一個元素，我們需要重新對它進行重新組合。在二進制堆中刪除

但在下面的鏈接，它說不可：

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

我對此有點困惑。

在此先感謝您的所有澄清。

來源

2011-09-28 Ruchi

二進制堆和其他優先級隊列結構通常不支持通用的「刪除元素」操作;您需要一個額外的數據結構來跟蹤堆中每個元素的索引，例如一個哈希表。如果你有，你可以實現一個通用的刪除操作

查找元素，O（1）預計的時間與哈希表
decrease key以低於最低，O（LG ñ） time
delete-min並更新散列表O（lg n）合併的預期時間。

來源

2011-09-28 12:02:53

感謝Larsmans！這意味着二進制堆只適用於按優先級排序數據。 – Ruchi

哪個PQ結構支持lgn刪除？ – Davidann

定期刪除是可能的，就像一個DeleteMin/Max。這個「問題」是你必須檢查上升和下降（即：當「最後」節點佔據空位時，它可能被過分評估或被低估，因爲它仍然不能同時存在原因是很容易檢查正確性

唯一的問題是查找上面的答案說明你可以在O（lg n）中查找元素，但我不知道如何在我的實現中，我通常構建一堆指向元素的指針而不是元素（在上/下移過程中更便宜地複製）。我爲元素類型添加了一個「位置」變量，它跟蹤了元素指針在堆中的索引。給定一個元素E，我可以發現它在堆中的位置是恆定的。

顯然，這並不是針對每個實現entation。

來源

2012-03-27 09:37:53 Gaminic

我很困惑爲什麼刪除二進制堆的操作被提及爲您的問題的鏈接中不可用。在二進制堆中刪除很有可能，它是二進制堆的其他操作的組成。 https://en.wikipedia.org/wiki/Binary_heap

我正在考慮你知道的二元堆

刪除從二元堆的一個關鍵要求兩行代碼/操作的所有其他操作。假設您想要刪除索引爲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

來源

2018-01-31 05:31:57

在二進制堆中刪除

回答

相關問題