优先级队列

队列的特点是什么?

聪明的小伙伴们都知道,是先进先出(FIFO)

那么,优先队列又是什么样子呢?

优先队列不再遵循先入先出的原则,而是分为两种情况:

最大优先队列,无论入队顺序,当前最大的元素优先出队。

最小优先队列,无论入队顺序,当前最小的元素优先出队。

比如有一个最大优先队列,它的最大元素是8,那么虽然元素8并不是队首元素,但出队的时候仍然让元素8首先出队:

要满足以上需求,利用线性数据结构并非不能实现,但是时间复杂度较高,最坏时间复杂度O(n),并不是最理想的方式。

回顾一下二叉堆的特性:最大堆的堆顶是整个堆中的最大元素;最小堆的堆顶是整个堆中的最小元素

因此,我们可以用最大堆来实现最大优先队列,每一次入队操作就是堆的插入操作,每一次出队操作就是删除堆顶节点。

入队操作:

出队操作:

二叉堆节点上浮和上沉的时间复杂度都是logn,所有优先级队列入队和出队的时间复杂度也是logn!


coding .....

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

友情链接更多精彩内容