什么是优先队列?

什么是优先队列?来自:程序员小灰(微信号:chengxuyuanxiaohui)这一次,我们来讲一讲二叉堆的另外一个应用:优先队列队列的特点是什么?聪明的小伙伴

欢迎大家来到IT世界,在知识的湖畔探索吧!

来自:程序员小灰(微信号:chengxuyuanxiaohui)

这一次,我们来讲一讲二叉堆的另外一个应用:优先队列

什么是优先队列?

队列的特点是什么?

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

入队列:

什么是优先队列?

出队列:

什么是优先队列?

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

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

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

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

什么是优先队列?

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

至于为什么最坏时间复杂度是O(n),大家可以思考下。

什么是优先队列?

让我们回顾一下二叉堆的特性:

  1. 最大堆的堆顶是整个堆中的最大元素
  2. 最小堆的堆顶是整个堆中的最小元素

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

入队操作:

  1. 插入新节点5
什么是优先队列?

  1. 新节点5上浮到合适位置。
什么是优先队列?

出队操作:

  1. 把原堆顶节点10“出队”
什么是优先队列?

  1. 最后一个节点1替换到堆顶位置
什么是优先队列?

  1. 节点1下沉,节点9成为新堆顶
什么是优先队列?

什么是优先队列?

什么是优先队列?

什么是优先队列?

public class PriorityQueue {
private int[] array;
private int size;
public PriorityQueue(){
//队列初始长度32
array = new int[32];
}
/**
* 入队
* @param key 入队元素
*/
private void enQueue(int key) {
//队列长度超出范围,扩容
if(size >= array.length){
resize();
}
array[size++] = key;
upAdjust();
}
/**
* 出队
*/
private int deQueue() throws Exception {
if(size <= 0){
throw new Exception("the queue is empty !");
}
//获取堆顶元素
int head = array[0];
//最后一个元素移动到堆顶
array[0] = array[--size];
downAdjust();
return head;
}
/**
* 上浮调整
*/
private void 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;
}
/**
* 下沉调整
*/
private void 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;
}
/**
* 下沉调整
*/
private void resize() {
//队列容量翻倍
int newSize = this.size * 2;
this.array = Arrays.copyOf(this.array, newSize);
}
public static void main(String[] args) throws Exception {
PriorityQueue priorityQueue = new PriorityQueue();
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());
}
}

欢迎大家来到IT世界,在知识的湖畔探索吧!

代码中采用数组来存储二叉堆的元素,因此当元素超过数组范围的时候,需要进行resize来扩大数组长度。

什么是优先队列?

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://itzsg.com/34469.html

(0)

相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

联系我们YX

mu99908888

在线咨询: 微信交谈

邮件:itzsgw@126.com

工作时间:时刻准备着!

关注微信