堆排序的空间复杂度是（），堆排序中构建堆的时间复杂度是（）。

[单选题]

堆排序的空间复杂度是（），堆排序中构建堆（自底向上）的时间复杂度是（）。

```
Ｏ(log(n))，O(n)
```
```
O(log(n))，O(nlog(n))
```
```
O(1)，O(n)
```
```
O(1)，O(nlog(n))
```

查看答案及解析

MyGoodHelper

“空间复杂度”指占内存大小，堆排序每次只对一个元素操作，是就地排序，所用辅助空间O(1)，空间复杂度是O（1）

在构建堆的过程中，完全二叉树从最下层最右边的非终端结点开始构建，将它与其孩子进行比较和必要的互换，对于每个非终端结点来说，其实最多进行两次比较和互换操作，因此整个构建堆的时间复杂度为O(n)。
在正式排序时，第i次取堆顶记录重建堆需要用O(logi)的时间（完全二叉树的某个结点到根结点的距离为⌊log2i⌋+1），并且需要取n-1次堆顶记录，因此，重建堆的时间复杂度为O(nlogn)。

编辑于 2016-05-15 20:54:10 回复(6)

SKCXY

该题中构建堆的意思应该是：在已有的数组上进行建堆，这种情况下，时间复杂度为O(n)应该就没什么疑问了。

本人看题的时候迷糊了下，将题中构建堆理解成，一个一个插入，此种情况下，时间复杂度是O(nlogn)。

发表于 2016-12-14 11:23:30 回复(0)

flowertree

构建堆，每个节点进入堆的时间复杂度为O(logn)，n个节点的话就为 O(nlogn)，构建完就是 O(nlogn)，真不懂C是怎么想的。

发表于 2016-02-13 16:08:17 回复(3)

Hi_Man

感觉是d，等下查一查

发表于 2016-08-06 09:10:28 回复(0)

七宝Wendy

初始化建堆过程时间：O(n)

更改堆元素后重建堆时间：O(nlogn)

发表于 2017-08-12 14:48:46 回复(0)

大星星和小猩猩

因为堆排序是原地排序，所以空间复杂度为O（1），而建堆的过程时间复杂度为O（N），可以看这里：https://www.zhihu.com/question/20729324

我把里面的观点提取一下：

假如有N个节点，那么堆的高度为H=logN。

其中，最后一层的每个父节点最多只需要下调1次，倒数第二层最多只需要下调2次，顶点最多需要下调H次。

而最后一层父节点共有2^(H-1)个,倒数第二层公有2^(H-2),顶点只有1(2^0)个。

所以最大的总共的时间复杂度为s = 1 * 2^(H-1) + 2 * 2^(H-2) + ... + (H-1) * 2^1 + H * 2^0

将H代入后s= 2N - 2 - log2(N)，所以时间复杂度为O(N)。

发表于 2018-03-21 08:44:47 回复(1)

Wilbur.

建堆？调整堆？区分了？

发表于 2022-08-09 12:38:00 回复(0)

代码裁缝

选C，注意是初始化堆还是重建堆，初始化堆的时间复杂度是O（n），重构堆的时间复杂度是O（nlogn）

发表于 2022-04-11 09:21:01 回复(0)

学术废物

CD是两种不同的插入方式

发表于 2022-03-14 10:55:57 回复(0)

牛客UESTC

“空间复杂度”指占内存大小，堆排序每次只对一个元素操作，是就地排序，所用辅助空间O(1)，空间复杂度是O（1）在构建堆的过程中，完全二叉树从最下层最右边的非终端结点开始构建，将它与其孩子进行比较和必要的互换，对于每个非终端结点来说，其实最多进行两次比较和互换操作，因此整个构建堆的时间复杂度为O(n)。在正式排序时，第i次取堆顶记录重建堆需要用O(logi)的时间（完全二叉树的某个结点到根结点的距离为⌊log2i⌋+1），并且需要取n-1次堆顶记录，因此，重建堆的时间复杂度为O(nlogn)。

发表于 2022-02-25 19:53:04 回复(0)