在堆排序的过程中，建立一个堆的时间复杂度是（）

[单选题]

```
O(n)
```
```
O(logn)
```
```
O(nlogn)
```
```
O(n2)
```

查看正确选项

Harmonia

22王道数据结构8.4.2 p315：建含n个元素的堆时，关键字的比较次数不超过4n，即可以在线性时间内建堆搬运思路： https://blog.csdn.net/qq_41647726/article/details/113278623

发表于 2021-04-24 12:40:00 回复(0)

AAS48

建堆时间复杂度：O(n)

调整堆、插入、删除：O(log2n)

堆排序平均时间复杂度：O(nlog2n)

空间复杂度：O(1)

记住！

发表于 2021-12-13 17:13:58 回复(1)

牛客129457616号

建堆时间复杂度：O(n)

调整堆、插入、删除：O(log₂n)

堆排序平均时间复杂度：O(nlog₂n)

空间复杂度：O(1)

发表于 2021-11-15 14:27:43 回复(0)

泽思

初始建堆时间复杂度O(n)，

一次重建堆时间复杂度O(logn)

堆排序时间复杂度为O(nlogn)，

发表于 2021-08-30 16:59:27 回复(0)

牛客4938kunn

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

发表于 2021-05-11 11:27:49 回复(0)