为什么通过插入元素构建堆的运行时比使用heapify更糟糕？

Question

在CLRS书中，通过自顶向下的heapify构建堆具有O(n)的复杂性。堆也可以通过反复调用插入来构建，在最坏的情况下，插入的复杂性为nlg(n)。

我的问题是:为什么后一种方法的性能较差？

我问这个问题是因为我觉得数学背后有一些简单的见解。例如,

快速排序、合并排序和堆排序都是基于减少不必要的比较，但方法不同。快速排序:平衡分区，不需要比较左子集和右子集。合并排序:简单地比较两个子数组中的两个最小元素。堆排序:如果A的值大于B，则A的值比B的后代大，不需要与他们进行比较。

Answer 1

两者的主要区别在于它们的工作方向:向上( O(n log )算法)或向下( O( n) )算法。

在通过进行n个插入所完成的O( n )算法中，每个插入都可能从(当前)堆的底部一直到顶部的一个元素冒泡。因此，假设除了最后一个完整的层之外，您已经构建了所有的堆。假设每次在该层中插入，所插入的值都是最小的总价值。在这种情况下，您必须将新元素一直泡到堆的顶端。在此期间，堆的高度(大致)为logn-1，因此您必须执行的交换的总数为(大致)n log /2-n/ 2，在最坏的情况下为Θ(n log )的运行时。

在通过一次构建堆完成的O(n)算法中，新元素被插入到各种较小堆的top中，然后开始冒泡。直观地说，堆中的元素越来越少，越高越高，所以大部分工作都花在叶子上，叶子比较高的元素低。

运行时的主要差异与方向有关。在O(n log )版本中，由于元素是冒泡的，运行时由从每个节点到树根的路径长度之和(即Θ(n log ))限制。在O(n)版本中，运行时受从每个节点到树叶的路径长度的限制，这要低得多(O(n))，因此更好的运行时。

希望这能有所帮助！