我要招人

去企业版

首页 > 试题广场 >

对于一个含n个元素的无序数组，构建一个大顶堆（Max-Hea

[单选题]

对于一个含n个元素的无序数组，构建一个大顶堆（Max-Heap），该操作的时间复杂度是？

```
O(n)
```
```
O(n^2)
```
```
O(log(n))
```
```
O(nlog(n))
```

查看正确选项

完善信息

求解…

发表于 2019-10-05 11:07:42 回复(2)

java狼人

初始化建堆时间复杂度是O(n),排序重建堆时间复杂度则为nlog(n)，觉得麻烦记住就好了，答案需要推导，详见 https://blog.csdn.net/qq_34228570/article/details/80024306

发表于 2019-11-03 13:10:15 回复(0)

不要把我当工具人

建堆有2种方法 1.HeapInsert: 假定我们事先不知道有多少个元素，通过不断往堆里面插入元素进行调整来构建堆。这种插入建堆的时间复杂度是O(NlogN) 2.Heapify: 从最后一个非叶子节点一直到根结点进行堆化的调整。如果当前节点小于某个自己的孩子节点（大根堆中），那么当前节点和这个孩子交换。这种建堆的时间复杂度是O(N)

发表于 2021-12-07 10:26:58 回复(1)

pein531

假设高度为k，则从倒数第二层右边的节点开始，这一层的节点都要执行子节点比较然后交换（如果顺序是对的就不用交换）；倒数第三层则会选择其子节点进行比较和交换，如果没交换就可以不用再执行下去了。如果交换了，那么又要选择一支子树进行比较和交换；高层也是这样逐渐递归。
那么总的时间计算为：s = 2^( i - 1 ) * ( k - i )；其中 i 表示第几层，2^( i - 1) 表示该层上有多少个元素，( k - i) 表示子树上要下调比较的次数。
S = 2^(k-2) * 1 + 2^(k-3)2…..+2(k-2)+2^(0)*(k-1) ===> 因为叶子层不用交换，所以i从 k-1 开始到 1；
S = 2^k -k -1；又因为k为完全二叉树的深度，而log(n) =k，把此式带入；
得到：S = n - log(n) -1，所以时间复杂度为：O(n)

编辑于 2021-02-13 17:20:59 回复(0)

_立夏本夏_

我咋觉得选

O(nlog n)

而不是选O(n)

求大佬解答

发表于 2020-06-18 21:54:03 回复(3)

汚兀武

自顶向下建堆得话是O(nlogn)，自底向上建堆得话是O(n)

发表于 2020-03-24 00:39:20 回复(0)

rogn

构建堆逐个插入的确是O(nlogn)，但是存在O(n)的构造方法

发表于 2020-03-03 23:54:29 回复(1)

猪小擎

<p>堆的insert操作是个logn的操作，构建n个就是nlogn，为什么答案是n？怎么可能有o1的isert操作？</p>

发表于 2020-12-01 23:20:53 回复(0)

HengV

题目说的是构建一个大顶堆，并不是初始化建堆啊，构建一个大顶堆需要后面的调整排序啊，为什么不选D呢？

发表于 2020-07-18 16:50:31 回复(0)

lvvvmd

这答案错的吧，难道不是nlogn吗

发表于 2019-10-05 13:12:57 回复(1)

提交观点

问题信息

算法工程师复杂度旷视 2019

上传者：小小

难度：

10条回答 178收藏 6861浏览

对于一个含n个元素的无序数组，构建一个大顶堆（Max-Hea

问题信息

热门推荐

相关试题