有关堆操作的时间复杂度

建堆和删除一个元素或者插入,维护堆不是一样的操作吗?为什么不是一样的复杂度呢#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

相关推荐

09-29 11:19
门头沟学院 Java
点赞 评论 收藏
分享
点赞 4 评论
分享
牛客网
牛客企业服务