摘要
队列的数据结构保证先进先出特性，优先级队列打破先进先出特性，制定优先级高的先出队规则。依然使用数组的数据结构，并且也要优化遍历和插入操作，就需要满足这两个添加的大顶堆来支持。所以优先级队列基于大顶堆实现是最优的选择。
队列是符合先进先出的特性，即先入队的元素先出队。那么把入队的元素设置优先级，在队列中按照优先级由高到低排序，就可以实现优先级高的先出队，这样的队列就是优先级队列。
队列是线性的数据结构，若入队一个有优先级的元素，就需要遍历队列中的元素，找到元素的合适位置。传统的做法可以每入队一个元素就要遍历整个队列，然后插入元素，遍历或者插入的时间复杂度是无法被忽略的。
现在要使用大顶堆的数据结构实现，来减少遍历或者插入的次数，达到优化优先级队列的目的（大顶堆可以查看上期内容）。为什么呢？
因为大顶堆的遍历类似二叉树，只会发生在节点和子节点之间。插入操作也是发生在节点与子节点之间的交换，并在最后空的位置放入元素，也就是二叉树的路径长度就是遍历或者插入操作的次数，这比线性结构（比如数组）的遍历和插入次数要少很多。
大顶堆的添加元素
先来梳理一下大顶堆添加元素和删除元素的代码逻辑，这部分的代码与上期介绍大顶堆的文章关联性比较大，建议不太熟悉大顶堆时，先看一下上期的文章。
先上大顶堆添加元素的代码：
public void add(E element) {
elementNotNullCheck(element);
ensureCapacity(size++);
elements[size -1] = element;
siftUp(size-1);
}
在代码中，首先要判断添加的元素是不是 null ，即 elementNotNullCheck() 方法：
private void elementNotNullCheck(E element) {
if (element == null) {
throw new IndexOutOfBoundsException("element is not null");
}
}
然后判断数组的容量是否够用，若不够用扩容数组，即 ensureCapacity() 方法，大致的逻辑如下：
1、 判断将要插入元素后的size是否大于原来的数组容量，若大于就往下走第2步；
2、 将数组的容量扩容为原来容量的1.5倍，即创建一个容量为原来1.5倍的新数组；
3、 将原来数组中的元素依次添加到新的数组中，完成；
具体的代码可以看之前介绍动态数组的那期，其中也有缩容的实现逻辑。
最后将元素放在数组的最后的位置（size-1)，并执行大顶堆的从 index 位置向上过滤方法（siftUp）将加入元素后的数组恢复成大顶堆性质。
大顶堆的删除元素
接下来是大顶堆删除元素的代码，实现的是删除堆顶元素并返回堆顶元素的逻辑：
public E remove() {
emptyCheck();
int lastIndex = -- size;
E root = elements[0];
elements[0] = elements[lastIndex];
elements[lastIndex] = null;
siftDown(0);
return root;
}
emptyCheck 是检查数组是否为空的方法，如果为空，就无法再进行删除：
private void emptyCheck() {
if (size == 0) {
throw new IndexOutOfBoundsException("Heap is empty");
}
}
删除元素的主要逻辑如下步骤，第 2 步是最核心的：
1、 先获取到堆顶元素，即索引为0元素，并size减1获取到最后元素的索引；
2、 最后索引的元素赋值到索引为0的元素，之后将最后索引位置赋值为null（即为删除元素）；
3、 最后从堆顶开始（即索引为0的位置）向下过滤（siftDown），恢复大顶堆结构；
优先级队列的主要方法
最后在大顶堆的基础上，实现优先级队列的几个主要方法就很简单了：
// 入队
public void enQueue(E element) {
heap.add(element);
}
// 出队
public E deQueue() {
return heap.remove();
}
// 获取队头元素，即数组中索引为 0 位置元素
public E front() {
return heap.get();
}
总结：
- 优先级队列用大顶堆实现可以减少遍历和插入的时间复杂度，提高效率；
- 大顶堆的添加和删除元素方法及逻辑；
- 优先级队列基于大顶堆实现入队、出队等方法。