漫画：什么是优先队列？

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

漫画：什么是二叉堆？（修正版）

漫画：什么是堆排序？

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

队列的特点是什么？

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

入队列：

出队列：

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

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

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

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

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

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

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

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

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

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

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

入队操作：

1.插入新节点5

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

出队操作：

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

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

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

public class PriorityQueue {

1. private int[] array;
2. private int size;
3. 

5. public PriorityQueue(){
6.    //队列初始长度32
7.    array = new int[32];
8. }
9. 

11. /**
12. * 入队
13. * @param key  入队元素
14. */
15. private void enQueue(int key) {
16.    //队列长度超出范围，扩容
17.    if(size >= array.length){
18.        resize();
19.    }
20.    array[size++] = key;
21.    upAdjust();
22. }
23. 

25. /**
26. * 出队
27. */
28. private int deQueue() throws Exception {
29.    if(size <= 0){
30.        throw new Exception("the queue is empty !");
31.    }
32.    //获取堆顶元素
33.    int head = array[0];
34.    //最后一个元素移动到堆顶
35.    array[0] = array[--size];
36.    downAdjust();
37.    return head;
38. }
39. 

41. /**
42. * 上浮调整
43. */
44. private void upAdjust() {
45.    int childIndex = size-1;
46.    int parentIndex = childIndex/2;
47.    // temp保存插入的叶子节点值，用于最后的赋值
48.    int temp = array[childIndex];
49.    while (childIndex > 0 && temp > array[parentIndex])
50.    {
51.        //无需真正交换，单向赋值即可
52.        array[childIndex] = array[parentIndex];
53.        childIndex = parentIndex;
54.        parentIndex = parentIndex / 2;
55.    }
56.    array[childIndex] = temp;
57. }
58. 

60. /**
61. * 下沉调整
62. */
63. private void downAdjust() {
64.    // temp保存父节点值，用于最后的赋值
65.    int parentIndex = 0;
66.    int temp = array[parentIndex];
67.    int childIndex = 1;
68.    while (childIndex < size) {
69.        // 如果有右孩子，且右孩子大于左孩子的值，则定位到右孩子
70.        if (childIndex + 1 < size && array[childIndex + 1] > array[childIndex]) {
71.            childIndex++;
72.        }
73.        // 如果父节点大于任何一个孩子的值，直接跳出
74.        if (temp >= array[childIndex])
75.            break;
76.        //无需真正交换，单向赋值即可
77.        array[parentIndex] = array[childIndex];
78.        parentIndex = childIndex;
79.        childIndex = 2 * childIndex + 1;
80.    }
81.    array[parentIndex] = temp;
82. }
83. 

85. /**
86. * 下沉调整
87. */
88. private void resize() {
89.    //队列容量翻倍
90.    int newSize = this.size * 2;
91.    this.array = Arrays.copyOf(this.array, newSize);
92. }
93. 

95. public static void main(String[] args) throws Exception {
96.    PriorityQueue priorityQueue = new PriorityQueue();
97.    priorityQueue.enQueue(3);
98.    priorityQueue.enQueue(5);
99.    priorityQueue.enQueue(10);
100.    priorityQueue.enQueue(2);
101.    priorityQueue.enQueue(7);
102.    System.out.println("出队元素：" + priorityQueue.deQueue());
103.    System.out.println("出队元素：" + priorityQueue.deQueue());
104. }

}

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

—————END—————