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

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

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

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

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

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

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