有关堆操作的时间复杂度

建堆和删除一个元素或者插入，维护堆不是一样的操作吗？为什么不是一样的复杂度呢#C++工程师#
全部评论
建堆O（n），删除O（logn），你想一下，现在有一个现成的堆，用数组存储表示，删除的话删掉堆顶元素，将数组最后一个数放到堆顶，整个堆里就只有这个新交换来的结点可能不满足堆的性质，那么只需要将这个结点依次向下转移，直到转移到符合堆性质的地方，转移的次数跟堆的高度有关，也就是O（logn），删除结点是有一个结点可能不满足堆性质，要调整，建堆过程是所有结点不满足要调整，所以，如果采用暴力建堆，也就是初始数组为空，每次插入一个结点然后调整满足堆性质，复杂度就是O(NlogN)，不过一般采用自底向上的下滤，对内部节点依次下滤，复杂度是O（n），建议看看清华邓俊辉的mooc视频，数据结构，讲的很清晰
点赞 回复 分享
发布于 2016-10-12 19:49
还有，合并堆的复杂度到底是多少，有没有推荐的好的网页
点赞 回复 分享
发布于 2016-10-12 18:48
buildHeap: O(N) deleteMin: O(logN) Ref: 《数据结构与算法分析 java语言描述》
点赞 回复 分享
发布于 2016-10-12 18:53
建议有时间去看看严书的数据结构，这种基础课程看看效果挺好的
点赞 回复 分享
发布于 2016-10-12 19:23

相关推荐

头像
今天 17:09
门头沟学院 前端工程师
点赞 评论 收藏
分享
11-25 00:31
上海交通大学 BSP工程师
点赞 评论 收藏
分享
10-30 13:45
南京理工大学 C++
点赞 评论 收藏
分享
11-08 10:39
门头沟学院 C++
点赞 评论 收藏
分享
11-25 14:30
CVTE_运营管理_HR
拿完offer再挑
目前池子里已经有很多同学泡着了，各个学校的三方也已经陆续开放，但是并不代表着签完三方就结束了，很多同学还会有违约考虑国企央企，所以10月到11月之间对于大部分同学来讲，还是没办法完全放松（已经拿到满意的offer的另说） ，还没有投的同学最后都投上吧，春招hc都不一定有秋招中期的剩下的hc多，直入主题，大家都关注的问题cvte加不加班？加还是加的，但是看部门，软硬件基本都是8点钟走其他的一些文职部门我看下班还是六点准时的而且不是强制，你事情做完可以走的，全天不打卡工资待遇怎么样？待遇还是挺不错，校招普遍都是10k以上，目前我见过最高的是18k的。福利待遇有哪些？五险一金啥的不用说了。住房公积...
CVTE公司福利 265人发布
点赞 评论 收藏
分享
点赞 4 评论
分享

招聘动态

查看更多

字节跳动

2025校园招聘

阿里云管培生

2025届校园招聘

快手Star

2025届招聘

快手

销售类投递专区

全站热榜

正在热议
# 25届秋招总结 #
346744次浏览 3361人参与
# 我的实习求职记录 #
6081317次浏览 83642人参与
# 阿里云管培生offer #
40650次浏览 831人参与
# 地方国企笔面经互助 #
5024次浏览 13人参与
# 职场吐槽大会 #
90035次浏览 742人参与
# 选完offer后，你后悔学本专业吗 #
22767次浏览 164人参与
# 北方华创开奖 #
39905次浏览 436人参与
# ai智能作图 #
1962次浏览 47人参与
# 运营商笔面经互助 #
92256次浏览 1331人参与
# 实习中的菜狗时刻 #
278446次浏览 2736人参与
# 如果有时光机，你最想去到哪个年纪？ #
24004次浏览 485人参与
# 风评不好的公司，你会去吗？ #
20623次浏览 94人参与
# 国企还是互联网，你怎么选？ #
89982次浏览 699人参与
# 软件开发2024笔面经 #
2324837次浏览 48213人参与
# 如何一边实习一边秋招 #
999343次浏览 12694人参与
# 远程面试的尴尬瞬间 #
20270次浏览 293人参与
# 银行笔面经互助 #
84553次浏览 893人参与
# 腾讯求职进展汇总 #
198027次浏览 1650人参与
# 第一份工作应该选择高薪还是大平台 #
88864次浏览 590人参与
# bilibili求职进展汇总 #
33864次浏览 361人参与
# 阿里求职进展汇总 #
70681次浏览 756人参与
# 上班苦还是上学苦呢？ #
79928次浏览 761人参与
牛客网
牛客企业服务