如何建立O（n）时间复杂度的最小-最大堆？ [英] How to build a Min-Max Heap in O(n) time complexity?

问题描述

我在Wikipedia上找到了最小最大堆的主题。我想知道是否有任何方法可以在 O（n）中构建此最小-最大堆。

I found the topic of min-max heap on Wikipedia. I was wondering if there is any way of building this min-max heap in O(n).

我知道您可以同时使用最小堆和最大堆，但是我不确定这样做的方法是什么。插入元素需要花费 O（log n）的时间复杂度，我觉得这种树无法比 O（n log n）。

I know you can do this with both min heap and max heap, but I'm not sure what would be the approach for this. Inserting an element takes O(log n) time complexity and I feel like this kind of tree can't be build more efficiently than O(n log n).

推荐答案

是的，可以。在 build-heap 循环中，您只需调用 TrickleDown ，就像使用最小堆或最大堆一样。该功能将根据项目的最小级别或最大级别相应地对其进行移动。

Yes, it can. In your build-heap loop, you simply call TrickleDown, just like you would with a min heap or a max heap. That function will move the item accordingly, depending on whether it's on a min level or a max level.

请参见原始文件，最小-最大堆和通用优先级队列了解一般信息。本文没有实现 build-heap ，但是如果您编写自己的调用 TrickleDown 的代码，它会按预期工作。即：

See the original paper, Min-Max Heaps and Generalized Priority Queues for general info. The paper doesn't implement build-heap, but if you write your own that calls TrickleDown, it works as expected. That is:

for i = A.length/2 downto 0
    TrickleDown(i)

TrickleDown 确定是否 i 处于最小级别或最大级别，并调用相应的方法 TrickleDownMin 或 TrickleDownMax 。

TrickleDown determines if i is on a min level or a max level, and calls the appropriate method, TrickleDownMin or TrickleDownMax.

这篇关于如何建立O（n）时间复杂度的最小-最大堆？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！