如何在最小最大堆上执行一般的删除操作？ [英] How to perform a general deletion operation on a min-max heap?

问题描述

注意：这个问题是由于我在网络上没有找到一个（正确的）解决方案，如何从最小 - 最大堆中删除任何节点。我作为答案提出的解决方案或不是正确的，因为我没有提供任何证明其正确性，只是解释。因此，这个问题的目的是为了强调算法和数据结构领域的专家来评论该解决方案，最终如果错误，提供一个具体且正确一个。我正在为整个社区做这个，而不仅仅是为了自己。

如何在最小最大堆上执行一般的删除操作？ p>

最小最大堆可用于实现双端优先级队列，因为它的时间不变 find-min 和 find-max 操作。我们还可以在 O（log ₂ n）时间中检索最小 - 最大堆中的最小和最大元素。有时候，我们也可能要删除min-max堆中的任何节点，这可以在 O（log ₂ n），根据（我认为是）原始文件介绍最小最大堆：

...

结构也可以广义地支持操作 Find（k）（确定结构中的第k个最小值），并且操作 k （删除结构中的第k个最小值），以对数时间为单位删除（k） >。

...

不知道他们是否指完全一般的删除任何节点...

解决方案

我不认为自己是专家的算法和数据结构，但是我对二进制堆有一个详细的了解，包括最小最大堆。参见例如我的二进制堆博客系列，从 http://blog.mischel.com/2013/09/29/a-better-way-to-do-it-the-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 
  

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

在您的示例中，由第一个操作（用31替换55）是无效的，因为31小于54.所以你必须把它泡在堆上。

另一件事：删除任意节点确实是一个log ₂ （n）操作。但是，除非您有其他数据结构跟踪堆中节点的位置，否则要查找要删除的节点是O（n）操作。因此，通常，将任意节点的删除视为O（n）。

Note: this question was induced by the fact that I've not found anywhere on the web a (correct) solution to "how to delete any node from a min-max heap". The solution that I present as an answer can or not be correct, since I don't present any proof of its correctness but just explanations. So, the purpose of this question is for experts in the field of algorithms and data structures to comment that solution and eventually, if it's wrong, provide one concrete and correct one. I'm doing this for the whole community, not just for myself.

How to perform a general deletion operation on a min-max heap?

A min-max heap can be useful to implement a double-ended priority queue because of its constant time find-min and find-max operations. We can also retrieve the minimum and maximum elements in the min-max heap in O(log₂ n) time. Sometimes, though, we may also want to delete any node in the min-max heap, and this can be done in O(log₂ n) , according to the (what I think is) original paper presenting 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.

...

Not sure though if they were referring exactly to a general "delete any" node...

解决方案

I don't consider myself an "expert" in the fields of algorithms and data structures, but I do have a detailed understanding of binary heaps, including the min-max heap. See, for example, my blog series on binary heaps, starting with http://blog.mischel.com/2013/09/29/a-better-way-to-do-it-the-heap/. I have a min-max implementation that I'll get around to writing about at some point.

Your solution to the problem is correct: you do indeed have to bubble up or sift down to re-adjust the heap when you delete an arbitrary node.

Deleting an arbitrary node in a min-max heap is not fundamentally different from the same operation in a max-heap or min-heap. Consider, for example, deleting an arbitrary node in a min-heap. Start with this min-heap:

      0
  4       1
5   6   2   3

Now if you remove the node 5 you have:

      0
  4       1
    6   2   3

You take the last node in the heap, 3, and put it in the place where 5 was:

      0
  4       1
3   6   2   

In this case you don't have to sift down because it's already a leaf, but it's out of place because it's smaller than its parent. You have to bubble it up to obtain:

      0
  3       1
4   6   2   

The same rules apply for a min-max heap. You replace the element you're removing with the last item from the heap, and decrease the count. Then, you have to check to see if it needs to be bubbled up or sifted down. The only tricky part is that the logic differs depending on whether the item is on a min level or a max level.

In your example, the heap that results from the first operation (replacing 55 with 31) is invalid because 31 is smaller than 54. So you have to bubble it up the heap.

One other thing: removing an arbitrary node is indeed a log₂(n) operation. However, finding the node to delete is an O(n) operation unless you have some other data structure keeping track of where nodes are in the heap. So, in general, removal of an arbitrary node is considered O(n).

这篇关于如何在最小最大堆上执行一般的删除操作？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！