1、优先队列模型

以最小元素优先级最高为例，优先队列是允许至少下列两种操作的模型：

  1. 插入元素：将新来的元素插入到优先队列的容器中
  2. 删除最小元素：找出、返回、并删除优先队列中的最小元素

优先队列（堆） - 图1

怎么去实现这样一个模型呢？

2、二叉堆

二叉堆是实现优先队列非常普遍的一种工具，以至于堆这个词不加修饰地使用在优先队列的上下文时，一般都是指优先队列的实现。

优先队列（堆） - 图2

2.1、二叉堆的结构性质

堆是一棵被完全填满的二叉树，有可能的例外是在底层，底层的元素从左到右填入，即是一棵完全二叉树。一颗高度为h的完全二叉树有 2 到 2-1 个节点，这也意味着完全二叉树的高度为⌊log N⌋。

由于完全二叉树的存储非常有规律，因此可以用数组而非链结构来表示它。对于数组中任意一个位置i上的元素，它的左儿子总是在位置2i上，右儿子总是在位置2i+1上，它的父亲节点总是在位置⌊i/2⌋上。例如上图中的完全二叉树可以表示为：

优先队列（堆） - 图3

2.2、二叉堆的堆序性质

让操作快速执行的性质是堆序性质。由于想要找到最小元，因此最小元应该在根节点上。如果考虑任何一棵子树也应该是一个堆，那么任意节点就应该小于它的所有后裔。

2.3、基本的堆操作

2.3.1、insert（插入）

为了将一个元素x插入到堆中，可在下一个可用位置创建一个空穴。如下：

优先队列（堆） - 图4

以插入x=14为例，由于将14插入空穴破坏了堆序性质（31>14），因此将需将31移入到空穴中：

优先队列（堆） - 图5

同样，21>14，所以将21移入到空穴中：

优先队列（堆） - 图6

重复这种策略，直到将14插入到正确位置：

优先队列（堆） - 图7

这种策略称为上滤。

2.3.2、deleteMin（删除最小元）

找到最小元是非常容易的，因为它就在根节点上，但是删除他之后会在根节点的位置出现一个空穴，由于堆中少了一个元素，因此 堆中最后一个元素x应该移动到它该去的位置，但是x不能直接移动到空穴里面去，因为这无法保证堆的堆序性。可以选择将空穴的两个儿子中较小的一个移动到空穴中，这样就把空穴推向了下一层，重复该步骤，直到x可以放入到空穴中（指空穴的左/右孩子节点的值都大于x或者空穴无左右孩子节点）。这个操作称之为下滤。看如下例子：

优先队列（堆） - 图8

2.3.3、buildHeap（构建堆）

将N个对象构造为一个堆，可以对这N个对象依次使用insert操作来完成。由于每个insert操作将花费O(1)平均时间和O(log N)最坏时间，因此算法的中运行时间是O(N)平均时间而不是O(N log N)的最坏时间。

2.4、代码实现

  1. class PriorityQue{
  2.     List<Integer> heap = null;
  4.     /**
  5.      * 构造一个空的优先队列
  6.      */
  7.     public PriorityQue(){
  8.         heap = new ArrayList<>();
  9.         heap.add(0);                //头部设置一个哑节点
  10.     }
  12.     /**
  13.      * 向优先队列中添加新的元素
  14.      * @param num 待添加的元素
  15.      */
  16.     public void insert(int num){
  17.         //先在可用位置添加一个空穴，然后进行上滤操作
  18.         heap.add(0);                //添加空穴
  19.         int hole = heap.size()-1;   //hole记录空穴位置
  20.         while (hole>0){
  21.             if(hole/2 < 1 || heap.get(hole/2)<num){         //空穴不存在父节点 或者 父节点的值小于num，直接将num填入空穴中
  22.                 heap.set(hole, num);
  23.                 break;
  24.             }else {                                         //否则进行上滤操作
  25.                 heap.set(hole, heap.get(hole/2));
  26.                 hole = hole/2;
  27.             }
  28.         }
  29.     }
  31.     public Integer deleteMin(){
  32.         if(heap.size()<=1){                                 //优先队列为空，返回null
  33.             return null;
  34.         }
  36.         Integer min = heap.get(1);                          //最小元在根节点，获取最小元
  37.         int hole = 1;                                       //根节点记录为空穴
  39.         while (hole*2 < heap.size()){                       //下滤 操作的必要条件：空穴还有孩子节点
  40.             if(heap.get(hole*2)>heap.get(heap.size()-1)
  41.                     && (hole*2+1 >= heap.size() || heap.get(hole*2+1)>heap.get(heap.size()-1))){ //如果当前空穴的左右孩子均大于最后一个元素的值，则不再下滤
  42.                 break;
  43.             }
  45.             //向左孩子下滤的条件：无右孩子 或者 左孩子的值小于右孩子的值
  46.             if(hole*2+1 >= heap.size() || heap.get(hole*2)<heap.get(hole*2+1)){
  47.                 heap.set(hole, heap.get(hole*2));
  48.                 hole = hole*2;
  49.             }else{  //向右孩子下滤的条件：右孩子的值小于左孩子的值
  50.                 heap.set(hole, heap.get(hole*2+1));
  51.                 hole = hole*2+1;
  52.             }
  53.         }
  54.         heap.set(hole, heap.get(heap.size()-1));            //将最后一个元素填入空穴
  55.         heap.remove(heap.size()-1);                   //删除最后位置的空穴
  56.         return min;
  57.     }
  58. }

参考：《数据结构与算法分析 Java语言描述》第三版