网站建设是广告么,有pc网站 移动网站怎么做,wordpress全站关闭评论,怎么做一个公众号微信转载自 漫画#xff1a;什么是优先队列
在之前的漫画中#xff0c;我们介绍了二叉堆和堆排序。没看过的小伙伴可以看一看前文#xff1a;
漫画#xff1a;什么是二叉堆#xff1f;#xff08;修正版#xff09;
漫画#xff1a;什么是堆排序#xff1f;
这一次什么是优先队列
在之前的漫画中我们介绍了二叉堆和堆排序。没看过的小伙伴可以看一看前文
漫画什么是二叉堆修正版
漫画什么是堆排序
这一次我们来讲一讲二叉堆的另外一个应用优先队列 队列的特点是什么 聪明的小伙伴们都知道是先进先出FIFO。
入队列 出队列 那么优先队列又是什么样子呢
优先队列不再遵循先入先出的原则而是分为两种情况
最大优先队列无论入队顺序当前最大的元素优先出队。
最小优先队列无论入队顺序当前最小的元素优先出队。
比如有一个最大优先队列它的最大元素是8那么虽然元素8并不是队首元素但出队的时候仍然让元素8首先出队 要满足以上需求利用线性数据结构并非不能实现但是时间复杂度较高最坏时间复杂度On并不是最理想的方式。
至于为什么最坏时间复杂度是On大家可以思考下。 让我们回顾一下二叉堆的特性
1.最大堆的堆顶是整个堆中的最大元素
2.最小堆的堆顶是整个堆中的最小元素
因此我们可以用最大堆来实现最大优先队列每一次入队操作就是堆的插入操作每一次出队操作就是删除堆顶节点。
入队操作
1.插入新节点5 2.新节点5上浮到合适位置。 出队操作
1.把原堆顶节点10“出队” 2.最后一个节点1替换到堆顶位置 3.节点1下沉节点9成为新堆顶 public class PriorityQueue {
private int[] array;
private int size;public PriorityQueue(){//队列初始长度32array 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());
}
}
代码中采用数组来存储二叉堆的元素因此当元素超过数组范围的时候需要进行resize来扩大数组长度。
