漫画：什么是优先队列？

野性酷女 2023-07-13 03:04 8阅读 0赞

在之前的漫画中，我们介绍了二叉堆和堆排序。没看过的小伙伴可以看一看前文：

[漫画：什么是二叉堆？（修正版）][Link 1]

[漫画：什么是堆排序？][Link 2]

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

![format_png][]

![format_png 1][]

队列的特点是什么？

聪明的小伙伴们都知道，是**先进先出（FIFO）**。

**入队列：**

![format_png 2][]

**出队列：**

![format_png 3][]

那么，优先队列又是什么样子呢？

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

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

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

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

**![format_png 4][]**

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

至于为什么最坏时间复杂度是O（n），大家可以思考下。

![format_png 5][]

![format_png 6][]

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

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

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

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

**入队操作：**

1.插入新节点5

![format_png 7][]

2.新节点5上浮到合适位置。

![format_png 8][]

**出队操作：**

1.把原堆顶节点10“出队”

![format_png 9][]

2.最后一个节点1替换到堆顶位置

![format_png 10][]

3.节点1下沉，节点9成为新堆顶

![format_png 11][]

![format_png 12][]

![format_png 13][]

![format_png 14][]

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());
    
    }
    
    }

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

![format_png 15][]

—————END—————

[Link 1]: http://mp.weixin.qq.com/s?__biz=MzIxMjE5MTE1Nw==&mid=2653195207&idx=2&sn=12689c6c1a92e7ec3cce4d423019ec2a&chksm=8c99f91dbbee700b8e760d06b27582037ab0713295dacf2b5a7a7f954c0032fe860aa0bf8b74&scene=21#wechat_redirect
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzIxMjE5MTE1Nw==&mid=2653195208&idx=1&sn=e3d6559402148458f0a4993b47d8bc6f&chksm=8c99f912bbee7004625a0b204acc8484acbdf4f1b18953e7ff5acbea958ec002d8c8ea072792&scene=21#wechat_redirect
[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3BCM0tyaWNyUkJlR0g2d3RZWTZSa3RZWTJTNXpjd0tRdm1oWTFwNVdUV1JMR3VMNlZPR0pqQVdrZWlhblliRmtYOUo2aGZ1YXZpYkdyZFEvNjQw?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3BCM0tyaWNyUkJlR0g2d3RZWTZSa3RZT1pJTUZENlZ4T3NtaGdyeksyQ29udlpoUVhGTVJtOGlia3UzSmFWbTRzWHh6RjJHaWE2Y2RBQlEvNjQw?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR3BCM0tyaWNyUkJlR0g2d3RZWTZSa3RZTXppY2p0WmliSGxpY0d5YWZXSG5LNzNONU44YUgxc2liNmh5OXVNNkcydldFbUY2aWNybFExSFVpYTNRLzY0MA?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR3BCM0tyaWNyUkJlR0g2d3RZWTZSa3RZQWtZbnducVl1UVNlOXBGaWI1b0Zkb25rRUdjblE4MldsZGxpYWFnOFl3eU5hQm5FOUlrUGZSQlEvNjQw?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR3BCM0tyaWNyUkJlR0g2d3RZWTZSa3RZbFRDd2hZd3pRMWljdjlNaWJJTk5pYXJtTGxmbGlhYnBxdk5seW1pYkpuOXhPNmdyRktRNm42TzRxdXcvNjQw?x-oss-process=image/format,png
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3BCM0tyaWNyUkJlR0g2d3RZWTZSa3RZUHlqQnpGTDdhVkVtaWJLeE1TRGVwbGcwRXBGYmNQM2MzZmYzWmttdTdCSzFlMlpOTmJ6cmdpYlEvNjQw?x-oss-process=image/format,png
[format_png 6]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3BCM0tyaWNyUkJlR0g2d3RZWTZSa3RZaWNnZzc5cGlhNEZtZG1TdjFpYnBoSFhMcXB6MG1lOFpEeEIyRUNLQkpEQklIdlRub1ZuMm1XY0hBLzY0MA?x-oss-process=image/format,png
[format_png 7]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR3BCM0tyaWNyUkJlR0g2d3RZWTZSa3RZaWNrb2FYb3dsTUR1VllxQTNPRFRXbHRhN2g4M2c2MTA2MjVpY0dEa3BQZGFNejJ3S05jeXRLbUEvNjQw?x-oss-process=image/format,png
[format_png 8]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR3BCM0tyaWNyUkJlR0g2d3RZWTZSa3RZSTlZcjRPaWFxNEQ5Y2JRMTcyNlhIa3Fkb1p6MU0zaWNwRE42UHhwWW93ajdpYjczWkdEaWFackZudy82NDA?x-oss-process=image/format,png
[format_png 9]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR3BCM0tyaWNyUkJlR0g2d3RZWTZSa3RZbXlFcGRLa2ZpYVRzRzdCVWhwOWNyREx5b0t3REJaSmliaWNQQk1JdmdWaWNMenR2Y0tJZ3YwQ0laZy82NDA?x-oss-process=image/format,png
[format_png 10]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR3BCM0tyaWNyUkJlR0g2d3RZWTZSa3RZV1JKM0ZvVkJwdFRPZnd5b250dWZqb0k0NGlhVlZhaWJ1djVhV1NXMWlhSkdDSk5rVlNVVEtQYTZ3LzY0MA?x-oss-process=image/format,png
[format_png 11]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9OdE81c2lhbEpaR3BCM0tyaWNyUkJlR0g2d3RZWTZSa3RZaGE5V0V6bllxVUFqTW5RbEdFdVBLcEw5OGNPT3g3aWNLRmxCV0drczVNT1JGSVJVN0c4VVd4QS82NDA?x-oss-process=image/format,png
[format_png 12]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3F5c2Q2eFJEanhnSUVJeDFGS1F4QTc4TEpuR3BrZGtuR1pxUGcxV1NXYkZQaEk0YldvTlpYU3p6a3ZBbFhYUFJFV0hRTE9MaWJmUmtnLzY0MA?x-oss-process=image/format,png
[format_png 13]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3F5c2Q2eFJEanhnSUVJeDFGS1F4QTdwbGxpY2ljdWljS1Z1aEJpY2FEazNDYVNsZ2hRMm5tUDUwVzF1VnFyRmx1OTZ3MlM2bHlOeGNvT2ZnLzY0MA?x-oss-process=image/format,png
[format_png 14]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3F5c2Q2eFJEanhnSUVJeDFGS1F4QTdxaWFDT1ZoaHBWTWZpY1E0V1Y0RVV2Z25XOE5qTnBPZEV4NTZXaWJOZ2V3WWFxUHhpY2tDdjJSa2RRLzY0MA?x-oss-process=image/format,png
[format_png 15]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3F5c2Q2eFJEanhnSUVJeDFGS1F4QTd0Yzc4NGliNkF5OXhRcHFRMGNDWUxFU1FZSXFuYzVTUWVpY0FBaWJpY3hTQWs5VngydFF2Q1V4R1RnLzY0MA?x-oss-process=image/format,png