当前位置: 首页> 教育> 高考 > 堆和优先级队列

堆和优先级队列

时间:2025/7/9 11:47:13来源:https://blog.csdn.net/RuanJian_GC/article/details/139484691 浏览次数:0次

堆的定义

堆必须是一个完全二叉树

大根堆:父节点元素都大于子节点元素

小根堆:父节点元素都小于子节点元素

完全二叉树的下标规律:若父节点下表为i,则左子节点下标为2i+1,右子节点下表为2i+2

堆的基本操作

两个基本操作:上滤/下滤

下滤:根节点向下调整 ,时间复杂度O(logn)

上滤:子节点向上调整,主要用于插入新元素到堆中,时间复杂度O(logn)

乱序数组建堆

自顶向下/自下而上

自顶向下建堆法 : 1. 插入堆(放入堆的最后一位) 2. 上滤

时间复杂度:O(nlogn)

自下而上建堆法 : 1. 建堆 2.每个父节点下滤,直到根节点操作完毕

时间复杂度:O(n)

优先级队列

插入队列:上滤

时间复杂度:O(logn)

弹出最小元素:弹出小根堆的根节点,把最后一个元素放在根节点,然后进行下滤操作

时间复杂度:O(logn)

堆排序

将优先级队列的所有元素依次弹出

考虑到空间复杂度,排序的结果会存放到堆空缺的单元里:用大根堆

时间复杂度:O(nlogn)

关键字:堆和优先级队列

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: