二进制堆中的删除

Question

我只是想学习二进制堆，并对在二进制堆中执行删除操作有疑问。 我读到我们可以从二进制堆中删除一个元素，并且需要重新堆化它。

但在以下链接中，它显示不可用：

http://en.wikibooks.org/wiki/Data_Structures /权衡

                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

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

• 使用哈希表实现一般删除操作作为查找元素，O(1) 预期时间
• 将 key 减少到小于最小值，O(lg n) 时间
• 删除最小值并更新哈希表，O(lg n）合并预期时间。

Answer 2

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

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

显然，这并不是针对每个实现的。

Answer 3

我很困惑为什么在您的问题的链接中提到二进制堆的删除操作不可用。二叉堆中的删除是很有可能的，它由二叉堆的另外两个操作组成。
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