algorithm - 如何在 O(n) 时间复杂度内构建 Min-Max Heap？

Question

我在 Wikipedia 上找到了min-max heap的主题。我想知道是否有任何方法可以在O(n).

我知道你可以用最小堆和最大堆来做到这一点，但我不确定这会是什么方法。插入一个元素需要O(log n)时间复杂度，我觉得这种树的构建效率不能比O(n log n).

Answer 1

是的，它可以。在您的构建堆循环中，您只需调用TrickleDown，就像使用最小堆或最大堆一样。该功能将相应地移动项目，具体取决于它是在最低级别还是最高级别。

有关一般信息，请参阅原始论文Min-Max Heaps 和 Generalized Priority Queues。该论文没有实现build-heap，但如果您编写自己的调用TrickleDown，它会按预期工作。那是：

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

TrickleDown确定i是在最低水平还是最高水平，并调用适当的方法，TrickleDownMin或TrickleDownMax。