关注
建堆O(n),删除O(logn),你想一下,现在有一个现成的堆,用数组存储表示,删除的话删掉堆顶元素,将数组最后一个数放到堆顶,整个堆里就只有这个新交换来的结点可能不满足堆的性质,那么只需要将这个结点依次向下转移,直到转移到符合堆性质的地方,转移的次数跟堆的高度有关,也就是O(logn),删除结点是有一个结点可能不满足堆性质,要调整,建堆过程是所有结点不满足要调整,所以,如果采用暴力建堆,也就是初始数组为空,每次插入一个结点然后调整满足堆性质,复杂度就是O(NlogN),不过一般采用自底向上的下滤,对内部节点依次下滤,复杂度是O(n),建议看看清华邓俊辉的mooc视频,数据结构,讲的很清晰
查看原帖
点赞 8
相关推荐
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 春招什么时候投? #
8305次浏览 135人参与
# 实习到现在,你最困惑的一个问题 #
3442次浏览 107人参与
# 春节前,你还在投简历吗? #
11465次浏览 137人参与
# 牛友的春节生活 #
5041次浏览 122人参与
# 牛客AI体验站 #
14283次浏览 262人参与
# 春节提前走,你用什么理由请假? #
7728次浏览 188人参与
# 从夯到拉,锐评职场mentor #
3612次浏览 56人参与
# 备战春招/暑实,现在应该做什么? #
3354次浏览 117人参与
# 距离春招还有一个月,你现在是什么开局? #
5190次浏览 101人参与
# 聊聊Agent开发 #
21494次浏览 549人参与
# 暑期实习什么时候投? #
5767次浏览 137人参与
# 推荐一个值得做的AI项目 #
5798次浏览 163人参与
# AI“智障”时刻 #
25699次浏览 127人参与
# 实习生应该准时下班吗 #
335463次浏览 1737人参与
# 用一句话形容你的团队氛围 #
38843次浏览 284人参与
# 总结:offer选择,我是怎么选的 #
258679次浏览 1508人参与
# 查收我的offer竞争力报告 #
276473次浏览 1693人参与
# 腾讯工作体验 #
568761次浏览 3715人参与
# 我的AI电子员工 #
27849次浏览 187人参与
# 实习的内耗时刻 #
221629次浏览 1644人参与
腾讯成长空间 6073人发布