algorithm - 如何删除最小-最大堆上的第 k 个元素？

Question

min-max 堆可用于实现双端优先级队列，因为它的 find-min 和 find-max 操作时间恒定。我们还可以在 O(log₂ n) 时间内检索最小-最大堆中的最小和最大元素。但有时，我们可能还想删除最小-最大堆中的任何节点，这可以在 O(log₂ n) 中完成，根据 paper which introduced min-max heaps :

...

The structure can also be generalized to support the operation Find(k) (determine the kth smallest value in the structure) in constant time and the operation Delete(k) (delete the kth smallest value in the structure) in logarithmic time, for any fixed value (or set of values) of k.

...

我如何准确地删除最小-最大堆上的第 k 个元素？

Answer 1

我不认为自己是算法和数据结构领域的“专家”，但我对二叉堆有详细的了解，包括最小-最大堆。例如，请参阅我关于二进制堆的博客系列，从 http://blog.mischel.com/2013/09/29/a-better-way-to-do-it-the-heap/ 开始.我有一个最小-最大实现，我会在某个时候写下来。

Your solution to the problem是正确的:当您删除任意节点时，您确实必须向上冒泡或向下筛选以重新调整堆。

删除最小-最大堆中的任意节点与最大堆或最小堆中的相同操作没有根本区别。例如，考虑删除最小堆中的任意节点。从这个最小堆开始:

      0
  4       1
5   6   2   3

现在，如果您删除节点 5，您将拥有:

      0
  4       1
    6   2   3

您将堆中的最后一个节点 3 放在 5 所在的位置:

      0
  4       1
3   6   2   

在这种情况下，您不必向下筛选，因为它已经是一片叶子，但它不合适，因为它比其父级小。您必须将其冒泡以获得:

      0
  3       1
4   6   2   

同样的规则适用于最小-最大堆。您将要删除的元素替换为堆中的最后一项，并减少计数。然后，您必须检查它是否需要起泡或过筛。唯一棘手的部分是逻辑根据项目是处于最低级别还是最高级别而有所不同。

在您的示例中，第一个操作(将 55 替换为 31)产生的堆无效，因为 31 小于 54。因此您必须将其向上冒泡到堆中。

另一件事:删除任意节点确实是一个 log₂(n) 操作。然而，找到要删除的节点是一个 O(n) 操作，除非您有一些其他数据结构来跟踪节点在堆中的位置。因此，一般来说，删除任意节点被认为是 O(n)。