algorithm - 为什么通过插入元素构建堆的运行时间比使用 heapify 差？

Question

在CLRS书中，自上而下的heapify构建堆的复杂度为O(n)。也可以通过反复调用插入来建立堆，其最坏情况下的复杂度为nlg(n)。

我的问题是:对于后一种方法性能较差的原因，是否有任何见解？

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

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

Answer 1

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

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

在通过一次性构建堆完成的 O(n) 算法中，新元素被插入到各种较小堆的顶部，然后向下冒泡。直觉上，堆中越来越高的元素越来越少，所以大部分工作都花在了叶子上，而叶子的位置比在较高的元素上要低。

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

希望这对您有所帮助!