什么是优先队列？漫画形式带你详细了解优先队列
这一次，我们来讲一讲二叉堆的另外一个应用：优先队列
队列的特点是什么？
聪明的小伙伴们都知道，是先进先出（FIFO）。
入队列：
出队列：
那么，优先队列又是什么样子呢？
优先队列不再遵循先入先出的原则，而是分为两种情况：
最大优先队列，无论入队顺序，当前最大的元素优先出队。
最小优先队列，无论入队顺序，当前最小的元素优先出队。
比如有一个最大优先队列，它的最大元素是8，那么虽然元素8并不是队首元素，但出队的时候仍然让元素8首先出队：
要满足以上需求，利用线性数据结构并非不能实现，但是时间复杂度较高，最坏时间复杂度O（n），并不是最理想的方式。
至于为什么最坏时间复杂度是O（n），大家可以思考下。
让我们回顾一下二叉堆的特性：
1.最大堆的堆顶是整个堆中的最大元素
2.最小堆的堆顶是整个堆中的最小元素
因此，我们可以用最大堆来实现最大优先队列，每一次入队操作就是堆的插入操作，每一次出队操作就是删除堆顶节点。
入队操作：
1.插入新节点5
2.新节点5上浮到合适位置。
出队操作：
1.把原堆顶节点10“出队”
2.最后一个节点1替换到堆顶位置
3.节点1下沉，节点9成为新堆顶
public class PriorityQueue {
privateint[] array;
privateint size;
publicPriorityQueue(){
//队列初始长度32
array =newint[32];
}
/**
* 入队
* @param key 入队元素
*/
privatevoid enQueue(int key){
//队列长度超出范围，扩容
if(size >= array.length){
resize();
}
array[size++]= key;
upAdjust();
}
/**
* 出队
*/
privateint deQueue()throwsException{
if(size <=0){
thrownewException("the queue is empty !");
}
//获取堆顶元素
int head = array[0];
//最后一个元素移动到堆顶
array[0]= array[--size];
downAdjust();
return head;
}
/**
* 上浮调整
*/
privatevoid upAdjust(){
int childIndex = size-1;
int parentIndex = childIndex/2;
// temp保存插入的叶子节点值，用于最后的赋值
int temp = array[childIndex];
while(childIndex >0&& temp > array[parentIndex])
{
//无需真正交换，单向赋值即可
array[childIndex]= array[parentIndex];
childIndex = parentIndex;
parentIndex = parentIndex /2;
}
array[childIndex]= temp;
}
/**
* 下沉调整
*/
privatevoid downAdjust(){
// temp保存父节点值，用于最后的赋值
int parentIndex =0;
int temp = array[parentIndex];
int childIndex =1;
while(childIndex < size){
// 如果有右孩子，且右孩子大于左孩子的值，则定位到右孩子
if(childIndex +1< size && array[childIndex +1]> array[childIndex]){
childIndex++;
}
// 如果父节点大于任何一个孩子的值，直接跳出
if(temp >= array[childIndex])
break;
//无需真正交换，单向赋值即可
array[parentIndex]= array[childIndex];
parentIndex = childIndex;
childIndex =2* childIndex +1;
}
array[parentIndex]= temp;
}
/**
* 下沉调整
*/
privatevoid resize(){
//队列容量翻倍
int newSize =this.size *2;
this.array =Arrays.copyOf(this.array, newSize);
}
publicstaticvoid main(String[] args)throwsException{
PriorityQueue priorityQueue =newPriorityQueue();
priorityQueue.enQueue(3);
priorityQueue.enQueue(5);
priorityQueue.enQueue(10);
priorityQueue.enQueue(2);
priorityQueue.enQueue(7);
System.out.println("出队元素："+ priorityQueue.deQueue());
System.out.println("出队元素："+ priorityQueue.deQueue());
}
}
代码中采用数组来存储二叉堆的元素，因此当元素超过数组范围的时候，需要进行resize来扩大数组长度。
—————END—————
●编号755，输入编号直达本文
●输入m获取文章目录
推荐↓↓↓
人工智能与大数据技术
更多推荐《18个技术类公众微信》
涵盖：程序人生、算法与数据结构、黑客技术与网络安全、大数据技术、前端开发、Java、Python、Web开发、安卓开发、iOS开发、C/C++、.NET、Linux、数据库、运维等。
-
fifo
+关注
关注
3文章
387浏览量
43646 -
数据结构
+关注
关注
3文章
573浏览量
40121 -
队列
+关注
关注
1文章
46浏览量
10891
原文标题：漫画：什么是优先队列？
文章出处：【微信号：TheAlgorithm，微信公众号：算法与数据结构】欢迎添加关注！文章转载请注明出处。
发布评论请先 登录
相关推荐
FIFO队列原理简述
请问使用邮箱、消息队列、信号量进行任务间通信时任务之间的切换要考虑优先级吗？
鸿蒙内核源码分析(调度队列篇)：进程和Task的就绪队列对调度的作用
干货 | RTOS应用中的优先级反转问题
cubeMX+STM32+Freertos读队列时阻塞相关资料分享
LabVIEW中的队列使用详解
带优先级队列的千兆以太网MAC设计
Linux IPC POSIX 消息队列
cubeMX+STM32+Freertos 读队列时阻塞
详细了解队列的特点及用处
队列Queue的常用方法有哪些
FreeRTOS消息队列介绍
工商网监
评论