1. 优先级队列的概念

前面我们学习了队列，队列是一种“先进先出”的数据结构，但是在一些的特定情况下，我们需要将一些优先级高的数据先出队列，这时普通的队列显然是无法满足的，这时就引进了优先级队列

2. 优先队列的模拟实现

在JDK1.8中，PriorityQueue优先级队列底层使用的是堆这种数据结构，而堆本质上是一颗完全二叉树

3 堆的概念

如果有一个关键码的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中，并满足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

4. 堆的存储方式

因为堆是一棵完全二叉树，所以可以层序的规则采用顺序的方式来高效存储

如果不是完全二叉树，则不适合采用该方式来存储，因为为了能够还原二叉树，空间中必须要存储空节点，就会导致空间利用率比较低

注意：

• 堆在逻辑上，结构是一个完全二叉树；而在实际存储结构中，是存储在一个数组中的

以大根堆为例：

假设堆中某个节点在数组中的下标为i

• 如果2i+1 < 数组长度（即节点个数），那么该节点存在左孩子，并且它的左孩子在数组中的下标为2i+1
• 如果2i+2 < 数组长度（即节点个数），那么该节点存在右孩子，并且它的右孩子在数组中的下标为2i+2
• 如果i不等于0，即该节点不是根节点，那么它的父亲节点是(i-1)/2

5. 堆向下调整

我们先考虑一种最简单的情况，假如一棵完全二叉树只有根节点不满足堆的概念，那么该怎么去调整这棵二叉树，使其成为一个堆呢？我们可以采用向下调整的方式

以调整为小根堆为例，对于下面这棵完全二叉树

观察该树，可知：根节点的左右子树都已经满足堆的性质了，只有根节点不满足，因此我们现在将根节点进行向下调整，步骤如下：

用代码实现的结果如下：

public void shiftDown(int[] array, int parent) {//childMin用来标记parent左右孩子的最小者//先用childMin标记parent的左孩子，因为parent可能有左孩子没有右孩子int childMin = 2 * parent + 1;//不断向下调整while(childMin < array.length) {//如果右孩子存在且左右孩子最小值为右孩子，则用childMin标记右孩子if(childMin + 1 < array.length && array[childMin] > array[childMin+1]) {childMin = childMin + 1;}if(array[parent] > array[childMin]) {//交换值int tmp = array[parent];array[parent] = array[childMin];array[childMin] = tmp;//交换值后，还需往后调整，因为交换值可能会破坏array[childMin]为根节点的堆结构parent = childMin;childMin = 2 * parent + 1;}else {//说明当前结构满足堆的性质break;}}}

注意： 在调整以parent为根的二叉树时，必须满足parent的左子树和右子树都已经是堆了，这样才能进行向下调整操作

时间复杂度分析： 最坏情况下，即parent一直向下调整到叶子节点，这时的时间复杂度就是树的高度，即O(log₂N )

6. 堆的创建

如果对于一个普通序列，不是只有根节点不满足堆的性质，那么该怎么去调整呢？下面以序列{1，5，3，8，7，6}为例，创建一个大根堆

步骤如下：

代码如下：

    public void createHeap(int[] array) {// 找倒数第一个非叶子节点，从该节点位置开始往前一直到根节点，遇到一个节点，应用向下调整int root = ((array.length-2)>>1);for (; root >= 0; root--) {shiftDown(array, root);}}

使用向下调整的方式建堆，时间复杂度为：O(N)
使用向上调整的方式建堆，时间复杂度为：O(Nlog₂N)

因此，在建堆时，使用向下建堆的效率更高

7. 堆的插入

在堆中插入元素都是将其放在数组的尾部（数组满了则需扩容），插入后可能会破坏堆的结构，这时就需要进行调整，需要从底部（插入元素的位置）开始往上调整，即向上调整，大致思路与向下调整一致

代码如下：

public void shiftUp(int child) {int parent = (child-1)/2;while(parent >= 0) {if(elem[parent] > elem[child]) {int tmp = elem[parent];elem[parent] = elem[child];elem[child] = tmp;child = parent;parent = (child-1)/2;}else {break;}}}

8. 堆的删除

注意：堆的删除，删除的是堆顶元素，即这棵完全二叉树的根节点，删除步骤如下：

1. 将堆顶元素和最后一个元素进行交换
2. usedSize–
3. 将堆顶元素向下调整

9. 用堆模拟实现优先级队列

完整代码如下:

import java.util.Arrays;
public class PriorityQueue {public int[] elem;public int usedSize;public PriorityQueue() {this.elem = new int[10];}public void initElem(int[] array) {for (int i = 0; i < array.length; i++) {this.elem[i] = array[i];this.usedSize++;}}public void shiftUp(int child) {int parent = (child-1)/2;while(parent >= 0) {if(elem[parent] > elem[child]) {int tmp = elem[parent];elem[parent] = elem[child];elem[child] = tmp;child = parent;parent = (child-1)/2;}else {break;}}}public void shiftDown(int parent, int usedSize) {//childMin用来标记parent左右孩子的最小者//先用childMin标记parent的左孩子，因为parent可能有左孩子没有右孩子int childMin = 2 * parent + 1;//不断向下调整while(childMin < usedSize) {//如果右孩子存在且左右孩子最小值为右孩子，则用childMin标记右孩子if(childMin + 1 < usedSize && elem[childMin] > elem[childMin+1]) {childMin = childMin + 1;}if(elem[parent] > elem[childMin]) {//交换值int tmp = elem[parent];elem[parent] = elem[childMin];elem[childMin] = tmp;//交换值后，还需往后调整，因为交换值可能会破坏elem[childMin]为根节点的堆结构parent = childMin;childMin = 2 * parent + 1;}else {//说明当前结构满足堆的性质break;}}}public void createHeap() {// 找倒数第一个非叶子节点，从该节点位置开始往前一直到根节点，遇到一个节点，应用向下调整for (int parent = (this.usedSize-1-1)/2; parent >= 0 ; parent--) {shiftDown(parent,this.usedSize);}}public void offer(int val) {if(isFull()) {elem = Arrays.copyOf(elem, 2*elem.length);}elem[usedSize] = val;shiftUp(usedSize);usedSize++;}public boolean isFull() {return usedSize == elem.length;}public boolean isEmpty() {return usedSize == 0;}public int poll() {if(isEmpty()) {return -1;}int tmp = elem[0];elem[0] = elem[usedSize-1];elem[usedSize-1] = tmp;usedSize--;return tmp;}public int peek() {if(isEmpty()) {return -1;}return elem[0];}
}