从2堆数据库中删除元素

Question

假设我们有两个不同的堆-第一个堆是最小堆，第二个堆是最大堆，它们包含n个不同的元素，没有两个不同的键，我需要删除元素x，它必须在其中一个堆中，但不是在两个堆中，因为这两个堆是不同的。

删除需要在O(logn)的复杂度内完成。

注意:堆的键可以按如下顺序排列：

minHeap: 6,6,6,6,6,6

maxHeap: 6,6,4,3

删除: x->key=6

你将如何做到这一点，有没有可能在想要的复杂性中做到这一点？

提示:您可以使用HeapChangeKey，它可以将元素x的键更改为您想要的任何内容-您可以使用它来冒泡您正在搜索的元素……(如果堆没有doubles，我有解决方案，但是没有人提前告诉我键是不同的，所以上面的例子就是我需要您帮助的原因)

Answer 1

您可以使用以下算法在O(log )时间内从二进制堆中删除：

1. 获取要删除的元素，并使用冒泡操作将其与其父元素交换，直到它到达堆的顶部。
2. 使用标准的二进制堆删除步骤来删除堆的顶部元素并重新平衡它。

第一步需要O(log )时间，因为您需要将元素一直交换到堆的顶部，这需要的时间与堆的高度成比例(O(log ))，第二步也需要O(log )。因此，如果您可以在O(log )时间内找到要从每个堆中删除的元素，则可以在O(log )时间内从两个堆中删除元素。

要做到这一点，一种方法是使用从堆中的值到其位置的哈希表或二进制搜索树来扩充这两个堆。这样，当您需要从一个或两个堆中删除一个条目时，您可以在哈希表中查找二进制堆中的位置来查找元素，然后可以使用上面的过程删除这些元素。您可能需要更新堆积元素的代码，以便在移动元素时更新这些表。

或者，如果不需要将元素存储在二进制堆中，则可以考虑将所有元素存储在平衡的二进制搜索树中。您可以在O(log )时间内对BST执行所有标准优先级队列操作，但也可以使用标准BST删除步骤在O(log )时间内轻松地从基于BST的优先级队列中删除元素。

希望这能有所帮助！