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

Question

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

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

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

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

谢谢。

Answer 1

您缺少 heapify 方法末尾的递归调用。

Heapify(A, i) {
   le <- left(i)
   ri <- right(i)
   if (le<=heapsize) and (A[le]>A[i])
      largest <- le
   else
      largest <- i 
   if (ri<=heapsize) and (A[ri]>A[largest])
      largest <- ri
   if (largest != i) {
      exchange A[i] <-> A[largest]
      Heapify(A, largest)
   }
}

在最坏的情况下，每一步之后，largest大约是i的两倍。要到达堆的末尾，需要 O(logn) 步。

Answer 2

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

          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)

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

Why is the time complexity of Heap Sort, O(nlogn)?

pseudocode

time-complexity

heapsort