大家好我是苏麟 , 今天聊聊优先队列 .
优先队列
我们了解优先队列之前先说说队列 .
队列的特点是什么？ 队列的特点是先进先出（FIFO）。
入队列，将新元素置于队尾：
出队列，队头元素最先被移出：
那么，优先队列又是什么样子呢？
优先队列不再遵循先入先出的原则，而是分为两种情况。
- 最大优先队列，无论入队顺序如何，都是当前最大的元素优先出队
- 最小优先队列，无论入队顺序如何，都是当前最小的元素优先出队
例如有一个最大优先队列，其中的最大元素是8，那么虽然8并不是队头元素， 但出队时仍然让元素8首先出队。
要实现以上需求，利用线性数据结构并非不能实现，但是时间复杂度较高。
优先队列的实现
先来回顾一下二叉堆的特性。
- 最大堆的堆顶是整个堆中的最大元素。
- 最小堆的堆顶是整个堆中的最小元素。
因此，可以用最大堆来实现最大优先队列，这样的话，每一次入队操作就是堆 的插入操作，每一次出队操作就是删除堆顶节点。 入队操作具体步骤如下。
1. 插入新节点5。
2. 新节点5“上浮”到合适位置。
出队操作具体步骤如下。
1. 让原堆顶节点10出队。
2. 把最后一个节点1替换到堆顶位置。
3. 节点1“下沉”，节点9成为新堆顶。
这里的代码跟堆排序差不多 , 这里就不展示了 .
小结
- 什么是二叉堆
二叉堆是一种特殊的完全二叉树，分为最大堆和最小堆。
在最大堆中，任何一个父节点的值，都大于或等于它左、右孩子节点的值。
在最小堆中，任何一个父节点的值，都小于或等于它左、右孩子节点的值。
- 什么是优先队列
优先队列分为最大优先队列和最小优先队列。
在最大优先队列中，无论入队顺序如何，当前最大的元素都会优先出队，这是 基于最大堆实现的。
在最小优先队列中，无论入队顺序如何，当前最小的元素都会优先出队，这是 基于最小堆实现的。
这期就到这里 , 下期见!
原文地址:https://blog.csdn.net/sytdsqzr/article/details/135445419
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.7code.cn/show_55366.html
如若内容造成侵权/违法违规/事实不符，请联系代码007邮箱：suwngjj01@126.com进行投诉反馈，一经查实，立即删除！
