1

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

...

对于任何固定值（或一组值），该结构还可以推广以支持在常数时间内进行操作Find(k)（确定结构中的第k个最小值）和在对数时间内进行操作Delete(k)（删除结构中的第 k 个最小值）的k。

...

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

4

2 回答 2

1

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

您对问题的解决方案是正确的：当您删除任意节点时，您确实必须冒泡或筛选以重新调整堆。

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

      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 2 (n) 操作。但是，查找要删除的节点是一个 O(n) 操作，除非您有一些其他数据结构来跟踪节点在堆中的位置。因此，一般来说，删除任意节点被认为是 O(n)。

于 2016-09-08T14:35:49.693 回答
-1

导致我开发这个解决方案（我不是 100% 肯定是正确的）的原因是我实际上找到了一个解决方案来删除最小-最大堆中的任何节点，但这是错误的。

可以在此处（在 C++ 中实现）和此处（在 Python 中实现）找到错误的解决方案。我将介绍刚才提到的错误Python的解决方案，每个人都更容易理解：

解决方案如下：

def DeleteAt(self, position):
    """delete given position"""
    self.heap[position] = self.heap[-1]
    del(self.heap[-1])
    self.TrickleDown(position)

现在，假设我们有以下最小-最大堆：

level 0                            10                        

level 1                92                       56           

level 2         41          54          23          11     

level 3      69    51    55    65    37    31

据我检查，这是一个有效的最小最大堆。现在，假设我们要删除元素 55，它在从 0 开始的数组中将在索引 9 处找到（如果我计算正确的话）。

上面的解决方案只需将最后一个元素放入数组中，在本例中为 31，并将其放在位置 9：

level 0                            10                        

level 1                92                       56           

level 2         41          54          23          11     

level 3      69    51    31    65    37    55

它将删除数组的最后一个元素（现在是 55），生成的最小-最大堆如下所示：

level 0                            10                        

level 1                92                       56           

level 2         41          54          23          11     

level 3      69    51    31    65    37

最后它会从position（即现在我们有数字 31 的地方）“涓涓细流”。

“trickle-down”将检查我们是否处于偶数（或最小）或奇数（或最大）级别：我们处于奇数级别（3），因此“trickle-down”将称为“trickle-down- max" 从 31 开始，但由于 31 没有孩子，所以它停止了（如果你不知道我在说什么，请查看上面的原始论文）。

但是，如果您观察到使数据结构处于不再是 min-max 堆的状态，因为 54 处于偶数级别，因此应该小于其后代，但大于其后代之一 31。

这让我觉得我们不能只看节点的子节点 at position，但我们还需要从那里position向上检查，也许我们也需要使用“涓涓细流”。

在下面的推理中，让我们删除我们想要删除的元素之后和任何修复操作运行之前的元素x。position让它p成为它的父母（如果有的话）。

我的算法的想法就是这样，更具体地说，是基于以下事实：

  1. Ifx位于奇数级别（如上面的示例中），我们将其与p位于偶数级别的 parent 交换，这不会破坏从 newx的位置向下的 min-max 堆的任何规则/不变量.

    • 如果情况相反，也可以进行相同的推理（我认为），即x最初处于平均位置并且它会大于其父级。

    • 现在，如果您注意到，唯一可能需要修复的是，如果x与它的父级交换并且它现在处于偶数（分别为奇数）位置，我们可能需要检查它是否小于（和分别大于）前一个偶数（和奇数）级别的节点。

这当然似乎不是我的全部解决方案，当然我还想检查xie的前一个父级p是否处于正确位置。

  • 如果p，在与 交换之后x，处于奇数（和分别为偶数）级别，则意味着它可能小于（并且分别大于）其任何后代，因为它之前处于偶数（和分别为奇数）级别。所以，我认为我们需要在这里“涓滴”。

  • 关于 ifp相对于其祖先处于正确位置这一事实，我认为推理与上述推理相似（但我不是 100% 确定）。

把这些放在一起，我想出了解决方案：

function DELETE(H, i):

    // H is the min-max heap array
    // i is the index of the node we want to delete
    // I assume, for simplicity, 
    // it's not out of the bounds of the array

    if i is the last index of H:
        remove and return H[i]
    else:
        l = get_last_index_of(H)

        swap(H, i, l)  

        d = delete(H, l)

        // d is the element we wanted to remove initially
        // and was initially at position i
        // So, at index i we now have what was the last element of H

        push_up(H, i)

        push_down(H, i)

        return d

这似乎根据我制作的最小-最大堆的实现起作用，您可以在此处找到。

另请注意，解决方案在O(log 2 n)时间内运行，因为我们只是调用按该顺序运行的“上推”和“下推”。

于 2016-09-08T13:54:50.417 回答