徘徊的路人甲
2016-10-12 19:49 未填写教育信息 后端工程师
关注
建堆O（n），删除O（logn），你想一下，现在有一个现成的堆，用数组存储表示，删除的话删掉堆顶元素，将数组最后一个数放到堆顶，整个堆里就只有这个新交换来的结点可能不满足堆的性质，那么只需要将这个结点依次向下转移，直到转移到符合堆性质的地方，转移的次数跟堆的高度有关，也就是O（logn），删除结点是有一个结点可能不满足堆性质，要调整，建堆过程是所有结点不满足要调整，所以，如果采用暴力建堆，也就是初始数组为空，每次插入一个结点然后调整满足堆性质，复杂度就是O(NlogN)，不过一般采用自底向上的下滤，对内部节点依次下滤，复杂度是O（n），建议看看清华邓俊辉的mooc视频，数据结构，讲的很清晰
查看原帖
点赞 8
相关推荐
点赞 评论 收藏
分享
04-03 11:24
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 面试体验最好和最差的公司 #
7411次浏览 53人参与
# 如何提高实习转正率？ #
99841次浏览 583人参与
# 厦门银行科技岗值不值得投 #
17256次浏览 413人参与
# 烂工作和没工作哪个更痛苦？ #
7975次浏览 155人参与
# 重来一次，我还会选择这个专业吗 #
444628次浏览 3947人参与
# 给工作过的公司写一条大众点评，你会怎么写？ #
3258次浏览 54人参与
# 春招至今，你收到几个面试了？ #
16954次浏览 276人参与
# 现在入门AI首先要做什么？ #
1665次浏览 51人参与
# AI替代不了什么？ #
6885次浏览 104人参与
# 一人分享一个skill #
1331次浏览 38人参与
# 银行笔面经互助 #
190282次浏览 1313人参与
# Agent面试会问什么？ #
5697次浏览 141人参与
# 总结:offer选择，我是怎么选的 #
280834次浏览 1552人参与
# 有必要和同事成为好朋友吗？ #
43916次浏览 439人参与
# 军工所铁饭碗 vs 互联网高薪资，你会选谁 #
10845次浏览 56人参与
# 学历VS实习，哪个更重要？ #
19343次浏览 258人参与
# 选完offer后，你后悔学本专业吗 #
68020次浏览 267人参与
# 面试线索爆料 #
123871次浏览 689人参与
# 职场吐槽大会 #
345085次浏览 2275人参与
# 如果实习可以转正，你会不会放弃秋招 #
969295次浏览 6875人参与
# 机械人，你的秋招第一份简历被谁挂了 #
261093次浏览 2435人参与