algorithm - 如何建立O(n)时间复杂度的最小-最大堆？

我在维基百科上找到了min-max heap的主题。我想知道是否有办法在O(n)中构建这个最小-最大堆。
我知道你可以同时使用最小堆和最大堆，但我不确定这是什么方法插入元素占用O(log n)时间复杂度，我觉得这种树不能比O(n log n)更有效地构建。

最佳答案

是的，可以。在构建堆循环中，只需调用TrickleDown，就像使用最小堆或最大堆一样。该函数将相应地移动该项，具体取决于它处于最低级别还是最高级别。
一般信息见原始文件，Min-Max Heaps and Generalized Priority Queues。本文没有实现构建堆，但是如果您自己编写调用TrickleDown的代码，它会按预期工作。即：

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

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