徘徊的路人甲
2016-10-12 19:49 未填写教育信息 后端工程师
关注
建堆O（n），删除O（logn），你想一下，现在有一个现成的堆，用数组存储表示，删除的话删掉堆顶元素，将数组最后一个数放到堆顶，整个堆里就只有这个新交换来的结点可能不满足堆的性质，那么只需要将这个结点依次向下转移，直到转移到符合堆性质的地方，转移的次数跟堆的高度有关，也就是O（logn），删除结点是有一个结点可能不满足堆性质，要调整，建堆过程是所有结点不满足要调整，所以，如果采用暴力建堆，也就是初始数组为空，每次插入一个结点然后调整满足堆性质，复杂度就是O(NlogN)，不过一般采用自底向上的下滤，对内部节点依次下滤，复杂度是O（n），建议看看清华邓俊辉的mooc视频，数据结构，讲的很清晰
查看原帖
点赞 8
相关推荐
牛客喵🐱：暑期实习/春招进度都在专题汇总页里，还有同阶段同学一起交流 👉https://www.nowcoder.com/link/chunzhaoji2610
查看7道真题和解析 点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# AI时代还有必要刷leetcode吗？ #
18047次浏览 285人参与
# 生化环材还是天坑吗 #
63250次浏览 336人参与
# 厦门银行科技岗值不值得投 #
27624次浏览 746人参与
# 有哪些公司在面试时考察AICoding？ #
13867次浏览 273人参与
# 薪资爆料 #
411324次浏览 2205人参与
# 从投递到OC，你用了多久 #
18371次浏览 196人参与
# 想从事Agent应该学习哪些技术？ #
5526次浏览 184人参与
# 多益网络工作体验 #
68084次浏览 309人参与
# 秋招报数：你投了多少家公司？ #
164179次浏览 971人参与
# 你都在哪些场所面过试？ #
79981次浏览 501人参与
# HR面都在聊什么？ #
10242次浏览 112人参与
# 你想吐槽公司的哪些规定 #
45594次浏览 211人参与
# 什么人最适合大厂？ #
10185次浏览 103人参与
# 哪些公司面试还在问八股？ #
10793次浏览 101人参与
# 父母问你工作找得怎么样，怎么回 #
18905次浏览 224人参与
# 如何快速融入团队？ #
48966次浏览 305人参与
# 我的求职进度条 #
1065321次浏览 7483人参与
# 26届春招投递记录 #
2682次浏览 32人参与
# 毕业论文进行时 #
35187次浏览 166人参与
# 技术转行的心路历程 #
93589次浏览 786人参与
# 你觉得mentor喜欢什么样的实习生 #
57992次浏览 1034人参与