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

二进制堆和其他优先级队列结构通常不支持一般的“删除元素”操作；您需要一个额外的数据结构来跟踪堆中每个元素的索引，例如哈希表。如果你有，你可以实现一个一般的删除操作

  • 查找元素，使用哈希表的 O(1) 预期时间
  • 将密钥减少到小于最小值，O(lg n ) 时间
  • delete-min 并更新哈希表，O(lg n ) 合并预期时间。
于 2011-09-28T12:02:53.470 回答
2

可以进行常规删除，就像 DeleteMin/Max 一样。“问题”是您必须同时检查升档和降档（即：当“最后一个”节点占据空位时，它可能被高估或低估。因为显然它仍然不能两者兼而有之原因，很容易检查正确性。

剩下的唯一问题是查找。上面的答案表明您可以在 O(lg n) 中查找元素，但我不知道如何。在我的实现中，我通常构建一个指向元素的指针而不是元素的堆（在升档/降档期间复制更便宜）。我向 Element 类型添加了一个“位置”变量，它跟踪堆中元素指针的索引。这样，给定一个元素 E，我可以在恒定时间内找到它在堆中的位置。

显然，这并不适用于每个实现。

于 2012-03-27T09:37:53.177 回答
0

我很困惑为什么在您的问题的链接中提到二进制堆的删除操作不可用。很有可能在二进制堆中删除，它是二进制堆的其他 2 个操作的组成。 https://en.wikipedia.org/wiki/Binary_heap

我在考虑你知道二进制堆的所有其他操作

从二进制堆中删除一个键需要 2 行代码/操作。假设您要删除 index 处的项目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-31T05:31:57.747 回答