堆排序中已经降序排序的数组的时间复杂度

Question

考虑一个已经按降序排序的数组 A[n]。堆已构建。现在考虑将 A[1](数组索引从 1 开始(与 A[heap.size] 交换的循环。这是伪代码：

Build-Max-Heap(A) //Already done
while (i > 0) {
     swap(A[1] with A[heap_size]
     heap_size = heap_size - 1
     Max-Heapify(A,1) //Takes lg(A.heap_size) time to float the 1st element down to it's respective position
} 

我们在元素 1 上调用 Max-Heapify 以通过允许它向下浮动到适当的位置来恢复堆属性。我们知道 Max-Heapify 需要c lg(n( 时间。那么，循环不应该取 c(lg (n( + lg (n-1( + .... + lg(1( ( = Theta(log(n(( 时间而不是 Theta (n*lg(n((？因为堆大小随着每次迭代而减小？

Answer 1

n..1的对数之和不是log(n)而是nlogn(看看斯特林公式(

从任意数组构建经典的堆是 O(n( 进程 - 而不是 O(nlogn(