performance - 为什么 BUILD-MAX-HEAP 需要时间 O(n) 而 HEAP-SORT 需要 O(nlgn) 时间？

Question

当我阅读“Introduction to Algorithms”时，我想知道为什么 HEAPSORT 需要时间 O(nlgn)，而 BUILD-MAX-HEAP 需要时间 O(n ).

HEAPSORT 在 A.length 下降到 2 处开始其 for 循环，调用 MAX-HEAPIFY。

BUILD-MAX-HEAP 在 A.length/2 向下到 1 的底部开始它的 for 循环，调用 MAX-HEAPIFY。

MAX-HEAPIFY 需要时间 O(lgn)。我想知道是什么导致 BUILD-MAX-HEAP 比 HEAPSORT 更快。

Answer 1

在构建堆时，我们总是从底部开始“HEAPIFY”元素，但在对其进行排序时，我们总是“HEAPIFY”最顶部的元素。在这两种情况下，高度都不同，但需要注意:

*在构建堆时，我们堆化的最大元素位于底部，它们堆化的高度非常小，因此 O(n)，但在排序时我们总是堆化最顶部的元素。即使高度正在降低，它也不像先前的情况那样有利。 *

我希望你能理解我想说的。