如何在最小-最大堆上执行第k个元素的删除？ [英] How do I perform a deletion of the kth element on a min-max heap?

问题描述

最小-最大堆可用于实现双端优先级队列，因为其恒定时间 find-min 和 find-max 操作。我们还可以在 O（log ₂ n）时间内检索最小-最大堆中的最小和最大元素。不过有时，我们可能还想删除min-max堆中的任何节点，这可以根据 O（log ₂ n）完成。 a href = http://www.akira.ruc.dk/~keld/teaching/algoritmedesign_f03/Artikler/02/Atkinson86.pdf rel = nofollow noreferrer>引入了最小最大堆的文件：

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 paper which introduced min-max heaps:

...

...

该结构也可以通用化以支持操作 Find（k）（确定结构中的 kth 最小值），并且操作 Delete（k） （删除结构中的第k个最小值）以对数时间表示，对于 k 的任何固定值（或一组值）。

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个元素最小/最大堆？

How exactly do I perform a deletion of the kth element on a min-max heap?

推荐答案

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

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.

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

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

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

Now if you remove the node 5 you have:

      0
  4       1
    6   2   3

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

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.

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

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.

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

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).

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