首页 > 试题广场 >

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

[不定项选择题]
对于根元素为最小值的二叉堆,下面说法正确的是
  • 删除最小元素的复杂度是o(logn)
  • 插入新元素的复杂度是o(1)
  • 合并两个堆的复杂度是o(logn)
  • 查询最小元素的复杂度是o(1)
A为什么错误?
发表于 2016-03-24 10:33:33 回复(7)

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

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

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

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

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

发表于 2016-03-23 21:04:32 回复(17)
B错,插入应该调整堆,复杂度为O(lgn)。至于C为什么错?合并两个堆有两种思路:1. 将一个堆的元素一个个插入另一个堆, O(n1 lgn2 );2. 直接复制另个堆的元素重建堆,O(n1 +n2 ), 因为建一个最大堆的时间复杂度为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)
关于A选项,删除最小元素之后不需要继续调整堆使其保持堆的性质吗?调整堆的O(lg n)的时间复杂度也得算在删除操作里面吧
发表于 2016-03-25 13:20:45 回复(5)
主要容易困惑的是C选项!我们都知道大顶堆或小顶堆的建堆最差情况下是O(n),而重新调整堆的时间复杂度为O(logn)。但是其实左式堆也是一种特殊的二叉堆,主要就是为了解决二叉堆合并操作的性能问题。
发表于 2016-07-03 09:58:35 回复(2)
因为建堆的时间复杂度是O(n)注意不是O(nlgn),所以合并两个普通的堆时间复杂度最多O(n), 但是采用左式堆等特殊的堆可以使合并复杂度变成 O(lgn)
发表于 2016-04-03 22:17:39 回复(1)

插入节点时间复杂度为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)
A选项中,删除最小元素后,要重新调整堆元素,使之保持最小堆。
发表于 2016-08-01 15:08:25 回复(0)
删除或插入新元素后,都要调整,所需时间复杂度为o(logn);
根结点已知为最小值,可直接查询,时间复杂度为o(1);
合并两个堆的时间复杂度应为o(nlogn);
发表于 2017-07-20 10:19:40 回复(0)
删除最小元素之后,需要继续调整使其保持堆的性质,即将堆中最后一个元素移动到堆顶,然后向下做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)
A:删除最小元素之后,将最后元素调到堆顶,然后进行重新排,时间复杂度为O(logn)
B:插入新元素,和删除一样,也是需要进行重排,时间复杂度为O(logn)
D:查询就是数组第一个元素,时间复杂度为O(1)
发表于 2017-06-15 20:28:47 回复(0)