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

Question

当我阅读“算法简介”时，我想知道为什么HEAPSORT需要时间 O(nlgn)，而BUILD-MAX-HEAP需要时间 O(n)。

开始它的 for 循环，HEAPSORT从 A.length 到 2，调用MAX-HEAPIFY.

从BUILD-MAX-HEAPA.length/2 到 1 开始它的 for 循环，调用MAX-HEAPIFY.

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

Answer 1

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

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

我希望你明白我想说什么。

Answer 2

在堆排序算法中，您总是担心“堆条件”，即不应将任何元素放在堆中大于更大元素的上方，如果有这样的元素违反堆条件，则修复它。修复堆条件需要多少努力取决于需要修复的元素在底部上方的高度。

在构建堆的初始阶段，后半部分元素不会违反堆条件，因为下面没有任何内容。四分之一的元素违反了堆条件，但仅比堆底部高一排，因此只需一步即可修复堆条件。那么八分之一的元素违反了堆条件，但是刚好在堆底上方两行，所以只需要两步。

如果将所需的步数相加，则得到 n/4 * 1 + n/8 * 2 + n/16 * 3 + n/32 * 4 ... 加起来小于 n。但是当你通过重复将第一个具有最大数字的元素放在数组末尾进行排序时，堆的顶部总是违反堆条件，底部上方有 (log n) 行，因此需要 log n 步修复堆条件。