题目

堆排序的空间复杂度是（），堆排序中构建堆的时间复杂度是（）。
（1）O(log(n))，O(n)
（2）O(log(n))，O(nlog(n))
（3）O(1)，O(n)
（4）O(1)，O(nlog(n))

答案

（3）O(1)，O(n)

堆排序是原地排序，所以空间复杂度是 O(1)

堆排序包括初始化建堆和堆排序。

1. 初始化建堆时间复杂度

假设数组包含N个元素，完全二叉树的高度H。前面我们提到初始化建堆时是从最后一个非叶子结点从右到左，从下到上将完全二叉树调整为大根堆的。那么每一层的节点个数和比较次数如下（注意我们是从最后一个非叶子结点开始比较的，所以最后一层比较次数为0）：

由此可知，初始化建堆时总的比较次数为：

根据等比数列求和，我们将等号左右两侧乘上2，得到：

后者减去前者得到：

对于完全二叉树而言结点个数N等于 ，因此在完全二叉树场景下H等于 （对于一般情形而言H等于 向下取整），代入H后得：

因此初始化建堆的时间复杂度近似为O(N)。

2. 堆排序时间复杂度

堆排序时我们每次将堆首和堆尾元素互换，然后重建堆。每一轮操作都意味着堆中会减少一个结点，重建时对应的时间复杂度（取决于堆的层数 ）也会下降。
对于N个结点的堆而言，二叉树高度H为 后向下取整，我们总共需要N-1次重建堆的操作。为了考虑取整带来的影响，我们倒推重建堆过程中的比较次数：

• 第N-1次重建堆时堆中仅剩下一个结点，高度为1，因此不需要额外的比较操作
• 第N-2和N-3次重建堆时，堆中包含2个结点，高度为2，因此需要1次额外的比较操作
• 第N-4~N-7次重建堆时，堆中包含4个结点，高度为3，因此需要2次额外的比较操作
• …
• 第1次重建堆时，堆中包含N-1个结点，高度为H，因此需要H-1次额外的比较操作

由此可得，N-1次重建堆总的比较次数s满足：

另外s满足：

代入H可以得到时间复杂度为 。

参考资料：堆排序中建堆过程时间复杂度O(n)怎么来的？https://www.zhihu.com/question/20729324