time-complexity - 为什么堆排序的时间复杂度是O(nlogn)？

Question

我试图了解不同数据结构的时间复杂度，并从堆排序开始。根据我的阅读，我认为人们共同同意堆排序的时间复杂度为 O(nlogn)；但是，我很难理解这是怎么回事。

大多数人似乎同意 heapify 方法采用 O(logn)，而 buildmaxheap 方法采用 O(n) 因此 O(nlogn)，但为什么 heapify 采用 O(logn)？

从我的角度来看，heapify 似乎只是一种比较节点的左右节点并根据它是最小堆还是最大堆来正确交换它们的方法。为什么需要 O(logn)？

我想我在这里遗漏了一些东西，如果有人能向我更好地解释这一点，我将不胜感激。

谢谢。

Answer 1

您似乎对堆排序的时间复杂度感到困惑。确实，从未排序的数组构建最大堆需要 O(n) 时间和 O(1) 来弹出一个元素。但是，从堆中弹出顶部元素后，您需要将堆中的最后一个元素 (A) 移动到顶部和 heapy 以维护堆属性。对于元素 A，它最多弹出 log(n) 次，这是堆的高度。因此，在弹出最大值后，最多需要 log(n) 次时间来获取下一个最大值。下面是堆排序过程的一个例子。

          18 

      15        8  

   7     11   1    2  

 3   6 4    9

弹出18的数字后，需要把数字9放在最上面堆化9。

          9

      15       8

   7     11  1   2

 3   6 4

我们需要弹出 9 因为 9 < 15

             15

          9       8

       7     11  1   2

     3   6 4

我们需要弹出 9 因为 9 < 11

          15

      11       8

   7     9  1   2

 3   6 4

9 > 4 这意味着 heapify 过程已经完成。现在您可以在不破坏堆属性的情况下安全地获得下一个最大值 15。

对于执行堆化过程所需的每个数字，您都有 n 个数字。所以heapsort的时间复杂度是O(nlogn)