algorithm - 为什么自上而下的堆构建方法效率低于自下而上，即使它的增长顺序低于 O(n)？

Question

O(n) 阶的堆构造的自下而上方法是怎样的？ Anany Levitin 在他的书中说，与 O(log n) 阶的自上而下方法相比，这更有效。为什么？

Answer 1

这对我来说似乎是一个错字。

有两种构建堆的标准算法。第一种是从一个空堆开始，然后一次一个地重复向其中插入元素。每个单独的插入都需要时间 O(log n)，因此我们可以将这种堆构建方式的成本上限设置为 O(n log n)。事实证明，在最坏的情况下，运行时间是 Θ(n log n)，如果您以反向排序的顺序插入元素，就会发生这种情况。

另一种方法是 heapify 算法，它通过从其自己的二进制堆中的每个元素开始并逐步将它们合并在一起来直接构建堆。无论输入如何，该算法的运行时间都是 O(n)。

第一个算法需要时间 Θ(n log n) 的原因是，如果你查看被插入的元素的后半部分，你会看到它们中的每一个都被插入到一个高度为 Θ 的堆中(log n)，因此每次冒泡的成本可能很高。由于有 n/2 个元素，每个元素都可能需要 Θ(log n) 的时间来插入，最坏情况下的运行时间是 Θ(n log n)。

另一方面，heapify 算法将大部分时间花在小堆上。一半的元素被插入到高度为 0 的堆中，四分之一插入到高度为 1 的堆中，八分之一插入到高度为 2 的堆中，等等。这意味着大部分工作都花在了将元素插入小堆中，这明显更快。