有关堆操作的时间复杂度
建堆和删除一个元素或者插入，维护堆不是一样的操作吗？为什么不是一样的复杂度呢#C++工程师#
2016-10-12 18:34 中南大学 Java
关注
全部评论
徘徊的路人甲
未填写教育信息 后端工程师
建堆O（n），删除O（logn），你想一下，现在有一个现成的堆，用数组存储表示，删除的话删掉堆顶元素，将数组最后一个数放到堆顶，整个堆里就只有这个新交换来的结点可能不满足堆的性质，那么只需要将这个结点依次向下转移，直到转移到符合堆性质的地方，转移的次数跟堆的高度有关，也就是O（logn），删除结点是有一个结点可能不满足堆性质，要调整，建堆过程是所有结点不满足要调整，所以，如果采用暴力建堆，也就是初始数组为空，每次插入一个结点然后调整满足堆性质，复杂度就是O(NlogN)，不过一般采用自底向上的下滤，对内部节点依次下滤，复杂度是O（n），建议看看清华邓俊辉的mooc视频，数据结构，讲的很清晰
匿名人士ABC
北京吉利学院 Java
buildHeap: O(N)
deleteMin: O(logN)
Ref: 《数据结构与算法分析 java语言描述》
牛客5709732号 楼主
楼主 中南大学 Java
还有，合并堆的复杂度到底是多少，有没有推荐的好的网页
ZJ_Lavender
中南大学 Java
建议有时间去看看严书的数据结构，这种基础课程看看效果挺好的
相关推荐
点赞 评论 收藏
分享
11-09 09:27
兰州大学 大数据开发工程师 点赞 评论 收藏
分享
09-24 10:27
焦作工贸职业学院 Java 
我的offer呢😡：这不才9月吗，26到明年毕业前能一直找啊
，能拿下提前批，转正的，offer打牌的都是有两把刷子的，为什么非要跟他们比。如果别人是9本硕+金牌+好几段大厂实习呢？如果别人是双非通天代呢？如果别人是速通哥呢？，做好自己就行了，我们做不到他们一样提前杀死比赛，但晚点到终点也没啥关系吧
点赞 评论 收藏
分享