对n个元素用插入法建堆的时间复杂度是（ &nbs...

[单选题]

对n个元素用插入法建堆的时间复杂度是（）

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

查看答案及解析

HengV

建堆有2种方法

第一种方法：HeapInsert（本题就是这种方法），它可以假定我们事先不知道有多少个元素，通过不断往堆里面插入元素进行调整来构建堆。这种插入建堆的时间复杂度是O(NlogN)

第二种方法：Heapify
从最后一个非叶子节点一直到根结点进行堆化的调整。如果当前节点小于某个自己的孩子节点（大根堆中），那么当前节点和这个孩子交换。这种建堆的时间复杂度是O(N)

Heapify是一种类似下沉的操作，HeapInsert是一种类似上浮的操作。

发表于 2020-07-15 10:35:01 回复(1)

Mrs_柳

快（快排）些（希尔）以O（n㏒n）的速度归（归并）队（堆）

发表于 2020-02-15 16:30:19 回复(2)

只有更坑，没有最坑

建堆难道不是初始化堆吗？

发表于 2020-03-08 14:49:10 回复(1)

酷CC

发表于 2021-11-23 23:49:57 回复(0)

zzhxufeng

单次heapInsert操作时间复杂度为O(N), 对每个元素都进行一次时间复杂度为O(N*logN)

发表于 2020-08-22 17:56:10 回复(0)

努力搬砖的小王

第一种方法HeapInsert 它可以假定我们事先不知道有多少个元素，通过不断往堆里面插入元素进行调整来构建堆。它的大致步骤如下：首先增加堆的长度，在最末尾的地方加入最新插入的元素。比较当前元素和它的父结点值，如果比父结点值大，则交换两个元素，否则返回。重复步骤2. 这种插入建堆的时间复杂度是O(NlogN) 第二种方法Heapify 从最后一个非叶子节点一直到根结点进行堆化的调整。如果当前节点小于某个自己的孩子节点（大根堆中），那么当前节点和这个孩子交换。Heapify是一种类似下沉的操作，HeapInsert是一种类似上浮的操作。这种建堆的时间复杂度是O(N)

发表于 2020-07-31 18:58:10 回复(0)