首页 > 试题广场 >

设某堆中有 n 个结点，则在该堆中插入一个新结点的时间复杂度

[单选题]
设某堆中有 n 个结点，则在该堆中插入一个新结点的时间复杂度为 O(log2n) 。 
  • 正确
  • 错误
查看正确选项
添加回答
哦哦哦5头像 哦哦哦5
查找，插入
发表于 2018-08-09 17:53:09 回复(0)
静墨客👄头像 静墨客👄
我需要帮忙解答疑惑，堆的时间复杂度不是nlog2n吗？
发表于 2017-10-29 18:50:51 回复(6)
牛客808325917号头像 牛客808325917号
不是很清楚，堆排序时间复杂度不是O(nlog2n)吗？
发表于 2021-12-13 16:10:59 回复(1)
洳果头像 洳果
在对内插入一个新的元素后，因为新插入的元素可能小于其孩子，这样就违背了最大堆的性质，就需要通过 一个MAX-HEAPIFY函数 让该顶点在最大堆中逐级下降，从而使得该节点重新获得最大堆的性质。
MAX-HEAPIFY（A,i）
1   l=LEFT(i)
2   r=RIGHT(i)
3   if l<=A.heap_size and A[l]>A[i]
4   largest=l
5   else 
6   largest=i
7   if r<=A.heap-size and A[r]>A[largest]
8   largest=r
9   if largest!=i
10 exchange A[i] and A[largest]
11 MAX-HEAPIFY（A,largest）
发表于 2020-06-16 11:03:07 回复(0)
Artorias_Sif头像 Artorias_Sif
某些特殊情况下，插入一个节点会退化成logn
发表于 2019-09-03 20:18:35 回复(0)
提交观点

问题信息

复杂度
上传者：阿奻_
难度：
5条回答 7596浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号