关注
建堆O(n),删除O(logn),你想一下,现在有一个现成的堆,用数组存储表示,删除的话删掉堆顶元素,将数组最后一个数放到堆顶,整个堆里就只有这个新交换来的结点可能不满足堆的性质,那么只需要将这个结点依次向下转移,直到转移到符合堆性质的地方,转移的次数跟堆的高度有关,也就是O(logn),删除结点是有一个结点可能不满足堆性质,要调整,建堆过程是所有结点不满足要调整,所以,如果采用暴力建堆,也就是初始数组为空,每次插入一个结点然后调整满足堆性质,复杂度就是O(NlogN),不过一般采用自底向上的下滤,对内部节点依次下滤,复杂度是O(n),建议看看清华邓俊辉的mooc视频,数据结构,讲的很清晰
查看原帖
点赞 8
相关推荐
牛客热帖
正在热议
# 拼多多求职进展汇总 #
236137次浏览 2038人参与
# ai智能作图 #
26598次浏览 315人参与
# 阿里云管培生offer #
61481次浏览 1756人参与
# 25届秋招总结 #
406145次浏览 4071人参与
# 25届机械人为了秋招做了哪些准备? #
25995次浏览 363人参与
# 地方国企笔面经互助 #
6810次浏览 16人参与
# 北方华创开奖 #
66713次浏览 551人参与
# 机械求职避坑tips #
23293次浏览 249人参与
# 实习,投递多份简历没人回复怎么办 #
2438958次浏览 34731人参与
# 软件开发投递记录 #
1480570次浏览 23940人参与
# 虾皮求职进展汇总 #
88510次浏览 714人参与
# 我的实习求职记录 #
6129097次浏览 84002人参与
# 我在牛爱网找对象 #
74699次浏览 554人参与
# 机械人怎么评价今年的华为 #
157660次浏览 1350人参与
# 你觉得通信/硬件有必要实习吗? #
54708次浏览 695人参与
# 歌尔求职进展汇总 #
42862次浏览 294人参与
# 如果可以,你希望哪个公司来捞你 #
33236次浏览 193人参与
# 如果再来一次,你还会选择这个工作吗? #
114236次浏览 1131人参与
# 如何写一份好简历 #
618590次浏览 8723人参与
# 在职场上,你最讨厌什么样的同事 #
5949次浏览 90人参与
# 硬件兄弟们 甩出你的华为奖状 #
78396次浏览 628人参与
# 你觉得第一学历对求职有影响吗? #
17695次浏览 155人参与