为什么自上而下的堆构建方法比自下而上的堆效率低，即使其增长顺序比O（n）低O（log n）？ [英] Why is the top down approach of heap construction less efficient than bottom up even though its order of growth is lower O(log n) over O(n)?

问题描述

O（n）阶堆构造的自底向上方法如何？ Anany Levitin在他的书中说，与自上而下的O（log n）阶方法相比，这种方法效率更高。为什么？

How is the bottom up approach of heap construction of the order O(n) ? Anany Levitin says in his book that this is more efficient compared to top down approach which is of order O(log n). Why?

推荐答案

在我看来，这是一个错字。

That to me seems like a typo.

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

There are two standard algorithms for building a heap. The first is to start with an empty heap and to repeatedly insert elements into it one at a time. Each individual insertion takes time O(log n), so we can upper-bound the cost of this style of heap-building at O(n log n). It turns out that, in the worst case, the runtime is Θ(n log n), which happens if you insert the elements in reverse-sorted order.

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

The other approach is the heapify algorithm, which builds the heap directly by starting with each element in its own binary heap and progressively coalescing them together. This algorithm runs in time O(n) regardless of the input.

第一个算法需要时间Θ（n log n）的原因是，如果您看一下在插入的元素的后半部分，您会看到每个元素都插入到高度为Θ（log n）的堆中，因此进行每次冒泡的成本可能很高。由于存在n / 2个元素，并且每个元素可能都需要花费时间θ（log n）才能插入，因此最坏的运行时是θ（n log n）。

The reason why the first algorithm requires time Θ(n log n) is that, if you look at the second half of the elements being inserted, you'll see that each of them is inserted into a heap whose height is Θ(log n), so the cost of doing each bubble-up can be high. Since there are n / 2 elements and each of them might take time Θ(log n) to insert, the worst-case runtime is Θ(n log n).

另一方面，heapify算法将大部分时间都花在小堆上。一半的元素插入到高度为0的堆中，四分之一插入到高度为1的堆中，八分之一插入到高度为2的堆中，依此类推。这意味着大部分工作都花在了将元素插入小堆中时，这要快得多。

On the other hand, the heapify algorithm spends the majority of its time working on small heaps. Half the elements are inserted into heaps of height 0, a quarter into heaps of height 1, an eighth into heaps of height 2, etc. This means that the bulk of the work is spent inserting elements into small heaps, which is significantly faster.

这篇关于为什么自上而下的堆构建方法比自下而上的堆效率低，即使其增长顺序比O（n）低O（log n）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！