首页 > 试题广场 >

对于根元素为最小值的二叉堆，下面说法正确的是

[不定项选择题]

删除最小元素的复杂度是o(logn)

```
插入新元素的复杂度是o(1)
```
```
合并两个堆的复杂度是o(logn)
```
```
查询最小元素的复杂度是o(1)
```

查看正确选项

Andre_Shi

A为什么错误?

发表于 2016-03-24 10:33:33 回复(7)

leobuzhi

根元素为最小值的二叉堆：

插入节点时间复杂度为O(log n)

删除节点时间复杂度为O(log n)

查询最小元素的复杂度是o(1)

合并两个堆的复杂度是o(lgn)

发表于 2016-03-23 21:04:32 回复(17)

westolife

B错，插入应该调整堆，复杂度为O(lgn)。至于C为什么错？合并两个堆有两种思路：1. 将一个堆的元素一个个插入另一个堆, O(n₁ lgn₂ )；2. 直接复制另个堆的元素重建堆，O(n₁ +n₂ ), 因为建一个最大堆的时间复杂度为O(n)。所以合并两个堆的复杂度不可能是O(lgn)。

编辑于 2016-09-17 11:55:31 回复(0)

黏黏糖

A.删除最小元素，即要调整堆，复杂度为O(logn)

B.插入新元素，要和堆中元素进行比较，寻找插入位置，复杂度为O(logn)

C.合并两个堆，即堆1的每个元素插入堆2，由B可得，复杂度为O(nlogn)

D.查询最小元素，小顶堆的最小元素即为堆顶，复杂度为O(1)

发表于 2017-05-23 20:59:02 回复(0)

abinge

关于A选项，删除最小元素之后不需要继续调整堆使其保持堆的性质吗？调整堆的O（lg n)的时间复杂度也得算在删除操作里面吧

发表于 2016-03-25 13:20:45 回复(5)

xiao_lai

主要容易困惑的是C选项！我们都知道大顶堆或小顶堆的建堆最差情况下是O(n)，而重新调整堆的时间复杂度为O(logn)。但是其实左式堆也是一种特殊的二叉堆，主要就是为了解决二叉堆合并操作的性能问题。

发表于 2016-07-03 09:58:35 回复(2)

dusj

因为建堆的时间复杂度是O(n)注意不是O(nlgn)，所以合并两个普通的堆时间复杂度最多O(n), 但是采用左式堆等特殊的堆可以使合并复杂度变成 O(lgn)

发表于 2016-04-03 22:17:39 回复(1)

June1993

插入节点时间复杂度为O(log n)

删除节点时间复杂度为O(log n)

查询最小元素的复杂度是o(1)

合并两个堆的复杂度是o(lgn)

发表于 2017-03-24 10:28:23 回复(0)

心海盗梦

A 删除最小元素的复杂度是O(logn)，这个无异议
B 插入元素：在下一个可用位置创建一个空穴，再将空穴上冒，复杂度O(logn)
C 合并两个堆的复杂度，如果是斐波那契堆，合并的复杂度是 O(1)，斜堆合并的时间复杂度是 O(lgN)如果是普通的堆，树形实现如 FreeBirdLjj 所言可以做到 O(lgN)。而数组实现，因为需要移动所有的元素，只能是 O(M+N)
D 查询最小元素的复杂度是o(1)，直接是根元素

发表于 2017-04-25 22:19:25 回复(0)

学术废物

前面做了道题搞混了

发表于 2022-03-06 16:09:33 回复(0)

夏小包

a 删除最小项的时间复杂度为O(1)，但是删除之后，需要重新调整堆的结构，重建堆的时间复杂度为O(logn)

发表于 2019-01-10 09:16:15 回复(0)

huixieqingchun

A选项中，删除最小元素后，要重新调整堆元素，使之保持最小堆。

发表于 2016-08-01 15:08:25 回复(0)

rppp

删除或插入新元素后，都要调整，所需时间复杂度为o(logn);

根结点已知为最小值，可直接查询，时间复杂度为o(1);

合并两个堆的时间复杂度应为o(nlogn);

发表于 2017-07-20 10:19:40 回复(0)

cppmeeposs

删除最小元素之后，需要继续调整使其保持堆的性质，即将堆中最后一个元素移动到堆顶，然后向下做heapify，时间复杂度为O(logn)；

合并两个堆有两种思路：1. 将一个堆的元素全部插入另一个堆--O(n1logn2)；2. 直接复制两个堆的元素重建堆--O(n1+n2)。因为建堆的时间复杂度为O(n)，所以合并两个普通堆的时间复杂度最多是O(n), 但是采用左式堆等特殊的堆可以使合并复杂度变成O(logn)。

发表于 2023-12-10 19:42:00 回复(0)

辉小歌

C是nlog2n 一开始觉得是log2n感觉堆顶合并一下，然后堆向下down一下即可。就一次down操作即可，每次down操作是log2n。但是你要知道合并前，俩堆是俩独立的数组，我们堆不能在俩树组上进行。我们传统意义上的堆操作是一个数组，u 2u 2u+1 祖先和他的左右儿子是有这样的关系。但是俩堆就不行了。故，合并只能是将一个堆的所有元素挨个插到另一个堆里。时间复杂度是nlog2n

发表于 2022-09-05 15:02:26 回复(0)

天尊墨宇

选AD

发表于 2020-07-19 07:24:25 回复(0)

笑以

左式堆呢？？？

发表于 2018-11-26 21:07:20 回复(0)

小龙马

C有问题吧，如果是链表堆的话，取其中一个堆底元素为根，两个堆的根分别为左子树和右子树，问题就转化为一个调整堆的问题了。如果堆只能用线性表实现的话那是我学艺不精。

发表于 2018-07-05 18:54:30 回复(0)

梦境迷离

C说的应该是向一堆中插入另一堆，mlogm没疑问

发表于 2018-01-22 16:03:16 回复(0)

sunlight_run

A：删除最小元素之后，将最后元素调到堆顶，然后进行重新排，时间复杂度为O(logn)

B：插入新元素，和删除一样，也是需要进行重排，时间复杂度为O(logn)

D：查询就是数组第一个元素，时间复杂度为O(1)

发表于 2017-06-15 20:28:47 回复(0)

提交观点

问题信息

堆

来自：2016乐视暑期实习生...

难度：

29条回答 1463收藏 13696浏览

对于根元素为最小值的二叉堆，下面说法正确的是

根元素为最小值的二叉堆：

插入节点时间复杂度为O(log n)

删除节点时间复杂度为O(log n)

查询最小元素的复杂度是o(1)

合并两个堆的复杂度是o(lgn)

插入节点时间复杂度为O(log n)

删除节点时间复杂度为O(log n)

查询最小元素的复杂度是o(1)

合并两个堆的复杂度是o(lgn)

问题信息

热门推荐

相关试题