徘徊的路人甲
2016-10-12 19:49 未填写教育信息 后端工程师
关注
建堆O（n），删除O（logn），你想一下，现在有一个现成的堆，用数组存储表示，删除的话删掉堆顶元素，将数组最后一个数放到堆顶，整个堆里就只有这个新交换来的结点可能不满足堆的性质，那么只需要将这个结点依次向下转移，直到转移到符合堆性质的地方，转移的次数跟堆的高度有关，也就是O（logn），删除结点是有一个结点可能不满足堆性质，要调整，建堆过程是所有结点不满足要调整，所以，如果采用暴力建堆，也就是初始数组为空，每次插入一个结点然后调整满足堆性质，复杂度就是O(NlogN)，不过一般采用自底向上的下滤，对内部节点依次下滤，复杂度是O（n），建议看看清华邓俊辉的mooc视频，数据结构，讲的很清晰
查看原帖
点赞 8
相关推荐
点赞 评论 收藏
分享
10-24 19:59
门头沟学院 Java 点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 第一次找实习，我建议__ #
17888次浏览 242人参与
# 你怎么评价今年的春招？ #
141361次浏览 1384人参与
# 从mentor身上学到了__ #
16038次浏览 261人参与
# 秋招暂停，我将对以下公司做出处罚__ #
28183次浏览 128人参与
# 什么样的公司千万别去 #
14642次浏览 110人参与
# 韶音科技求职进展汇总 #
59350次浏览 504人参与
# 你听到的“最没用”的秋招建议 #
19413次浏览 222人参与
# 如果今天是你的last day，你会怎么度过？ #
46952次浏览 294人参与
# 外出实习被同学举报 #
2743次浏览 29人参与
# 秋招我要惩罚这些公司 #
2324次浏览 22人参与
# 2025秋招体验点评 #
45295次浏览 466人参与
# 军工所铁饭碗 vs 互联网高薪资，你会选谁 #
3735次浏览 18人参与
# 你认为工作的意义是什么 #
201510次浏览 1268人参与
# 工作以后，你父母对你啥态度 #
8610次浏览 90人参与
# 打工人的至爽时刻or至暗时刻 #
41275次浏览 221人参与
# 在国企工作的人，躺平了吗？ #
374807次浏览 3930人参与
# 秋招结束之后的日子 #
105284次浏览 1016人参与
# 实习生的蛐蛐区 #
834925次浏览 4092人参与
# 你的秋招第一面感觉怎么样 #
127762次浏览 795人参与
# 非技术岗简历怎么写 #
259730次浏览 3103人参与