优先级队列（堆）-蒲公英云

优先级队列

概念

我们知道，队列是一种先进先出的数据结构，但有些情况下，操作的数据可能带有优先级，一般出队列时，可能需要优先级高的元素先出队列，该中场景下，使用队列显然不合适，比如在使用手机玩游戏的时候，如果有来电，那么系统应该优先处理打进来的电话；有的班主任可能会让成绩好的同学先挑选座位。

在此类情况下，数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。这种数据结构就是优先级队列。

优先级队列的模拟实现

JDK1.8中的PriorityQueue底层使用了堆这种数据结构，而堆实际上是在完全二叉树的基础上进行了一些调整。

堆的概念

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

堆的性质：
1.堆中某个结点的值总是不小于或者不大于父节点的值；

2.堆总是一棵完全二叉树。

堆的存储方式

从堆的概念可知，堆是一棵完全二叉树，因此可以层序的规则采用顺序的方式来高效存储。

将元素存储到数组中后，可以利用以下性质对树进行还原。假设i为结点在数组中下标，则有：

1.如果i为0，则i表示的节点为根节点，否则i结点的双亲结点为(i-1)/2.

2.如果2 * i + 1小于节点个数，则结点i的左孩子下标为2 * i + 1,否则没有左孩子

3.如果2 * i + 2小于节点个数，则结点i的右孩子下标为2 * i + 2,否则没有右孩子

堆的创建

堆向下调整

对于集合{27, 15, 19, 18, 28, 34, 65, 49, 25, 37}中的数据，如何将其创建成小根堆呢？

观察上图后发现：根结点的左右子树已经完全满足堆的性质，因此只需将根结点向下调整好即可。

向下调整的过程（以小堆为例）：

让parent标记需要调整的结点，child标记parent的左孩子(注意：parent如果有孩子一定是先有的左孩子)

2.如果parent的左孩子存在，即:child < size(完全二叉树的大小),进行以下操作，直到parent的左孩子不存在。

（1）判断parent的右孩子是否存在，存在找到左右孩子中最小的孩子，让child进行标记

（2）将parent与较小的孩子进行比较，如果：parent小于较小的孩子child，调整结束；否则：交换parent与较小的孩子child，交换完成后，parent中大的元素向下移动，可能导致子树不满足对的性质，因此需要继续向下调整，即:parent = child; child = 2*parent+1,后继续2.

具体代码如下：

public void shiftDown(int[] array, int parent) {
        //child先标记parent的左孩子，因为parent可能有左没有右
        int child = 2 * parent + 1;
        int size = array.length;
        while(child < size) {
            //如果右孩子存在，找到左右孩子中较小的孩子，用child进行标记
            if(child + 1 < size && array[child + 1] < array[child]) {
                child++;
            }
            //如果双亲比其最小的孩子还小，说明该结构已经满足堆的特性了
            if(array[parent] <= array[child]) {
                break;
            } else {
                //将双亲与较小的孩子交换
                int t = array[parent];
                array[parent] = array[child];
                array[child] = t;
                //parent中大的元素往下移动，可能会造成子树不满足堆的性质，因此需要继续向下调整
                parent = child;
                child = 2 * parent + 1;
            }
        }
    }

注意：在调整以parent为根的二叉树时，必须要满足parent的左子树和右子树已经是堆了才可以向下调整。

时间复杂度分析：最坏的情况即如图所示的情况，从根一路比较到叶子，比较的次数为完全二叉树的高度，即时间复杂度为O(log2 n)

堆的创建

那对于普通的序列{1,5,3,8,7,6},即根结点的左右子树都不满足堆的特性，又该如何调整呢？

参考代码：

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

最终的时间复杂度：O(n),可自行进行推导。

堆的插入与删除

堆的插入

堆的插入总共需要两个步骤：

1.先将元素放入到底层空间中（注：空间不够时需要扩容）

2.将最后新插入的结点向上调整，直到满足堆的性质。

与向下调整类似，让我们先来看一下向上调整的代码。

public void shiftUp(int array[], int child) {
        //找到child的双亲
        int parent = (child - 1) / 2;
        while(child > 0) {
            //如果双亲比孩子小，parent满足堆的性质，调整结束
            if(array[parent] < array[child]) {
                break;
            } else {
                //将双亲与孩子结点进行交换
                int t = array[parent];
                array[parent] = array[child];
                array[child] = t;
                //小的元素向下移动，可能到值子树不满足对的性质，因此需要继续向上调增
                child = parent;
                parent = (child - 1) / 2;
            }
        }
    }

堆的删除

注意：堆的删除一定删除的是堆顶元素。具体如下：

1.将堆顶元素对堆中最后一个元素交换

2.将堆中有效数据的个数减少一个

3.对堆顶元素向下调整

代码也很简单：

public static void poll(int[] array, int size) {
        //交换顶和末元素,size为当前数组大小
        int tmp = array[0];
        array[0] = array[--size];
        array[--size] = array[0];
        shiftDown(array, array[0]);
    }

常用接口介绍

PriorityQueue的特性

Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列，PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的，本文主要介绍PriorityQueue.

关于PriorityQueue的使用要注意：
1.使用时必须导入PriorityQueue所在的包，即：

import java.util.PriorityQueue;

2.PriorityQueue中放置的元素必须能够比较大小，不能插入无法比较大小的对象，否则会抛出ClassCastException异常

3.不能插入null对象，否则会抛出NullPointerException

4.没有容量限制，可以插入任意多个元素，其内部可以自动扩容

5.插入和删除元素的时间复杂度为O(log2 n)

6.PriorityQueue底层使用了堆数据结构

7.Priority默认情况下是小堆，即每次获得到的元素都是最小的元素

PriorityQueue常用接口介绍

1.优先级队列的构造

此处只是列出了PriorityQueue中几种常见的构造方式，其它的可以借助Api查询

构造器	功能介绍
PriorityQueue()	创建一个空的优先级队列，默认容量是11
PriorityQueue(int initialCapacity)	创建一个初始容量为initialCapacity的优先级队列，注意：initalCapacity不能小于1，否则会抛出IllegalArgumentException异常
PriorityQueue(collection<? extends E> c)	用一个集合来创建优先级队列

举个例子简要介绍一下它的构造：

public static void TestPriorityQueue() {
        //创建一个空的优先级队列，底层默认容量是11
        PriorityQueue<Integer> q1 = new PriorityQueue<>();
        //创建一个空的优先级队列，底层的容量为initalCapacity
        PriorityQueue<Integer> q2 = new PriorityQueue<>(100);
        ArrayList<Integer> list = new ArrayList<>();
        list.add(4);
        list.add(3);
        list.add(2);
        list.add(1);
        //用ArrayList对象来构造一个优先级队列的对象
        PriorityQueue<Integer> q3 = new PriorityQueue<>(list);
        System.out.println(q3.size());
        System.out.println(q3.peek());
    }

注意：默认情况下，PriorityQueue队列是小堆，如果需要大堆需要用户提供的比较器

代码样例如下：

static class IntCmp implements Comparator<Integer> {
     @Override
     public int compare(Integer o1, Integer o2) {
        return o2 - o1;//这里的比较使最终创建结果为大根堆
     }
}
 public static void main(String[] args) {
        //表明该优先级队列使用的是用户自己提供的比较器
        PriorityQueue<Integer> p = new PriorityQueue<>(new IntCmp());
        p.offer(4);
        p.offer(3);
        p.offer(2);
        p.offer(1);
        p.offer(5);
        System.out.println(p.peek());
    }

此时创建出的就是一个大堆。

2.插入/删除/获取优先级最高的元素

函数名	功能介绍
boolean offer(E e)	插入元素e，插入成功返回true，如果e对象为空，则抛出NullPointerException异常，时间复杂度为O(log2 n),注意：空间不够的时候会进行扩容
E peek()	获取优先级最高的元素，如果队列的优先级为空，返回null
E poll()	移除优先级最高的元素并返回，如果优先级队列为空，返回null
int size()	获取有效元素的个数
void clear()	清空
boolean isEmpty()	检测优先级队列是否为空，空返回true

代码示例如下：

public static void TestPriorityQueue2() {
        int arr[] = {4, 1, 9, 2, 8, 0, 7, 3, 6, 5};
        //一般在创建优先级队列对象时，如果知道元素个数，建议就直接将底层容量给好
        //否则在插入当中不断需要扩容
        //扩容机制：开辟更大的空间，拷贝元素，这样效率会比较低
        PriorityQueue<Integer> q = new PriorityQueue<>(arr.length);
        for(int e : arr) {
            q.offer(e);
        }
        System.out.println(q.size());
        System.out.println(q.peek());
        //从优先级队列中删除连个元素之和，再次获取优先级最高的元素
        q.poll();
        q.poll();
        System.out.println(q.size());
        System.out.println(q.peek());
        q.offer(0);
        System.out.println(q.peek());
        //将优先级队列中的有效元素删除掉，检测其是否为空
        q.clear();
        if(q.isEmpty()) {
            System.out.println("优先级队列已经为空！！！");
        } else {
            System.out.println("优先级队列不为空");
        }
    }

注意：以下是JDK1.8当中，PriorityQueue的扩容方式：

privatestaticﬁnalintMAX_ARRAY_SIZE=Integer.MAX_VALUE-8;
privatevoidgrow(intminCapacity){
 intoldCapacity=queue.length;
  //Doublesizeifsmall; elsegrowby50%
  intnewCapacity=oldCapacity+((oldCapacity<64)?
                  (oldCapacity+2):
                  (oldCapacity>>1));
  //overﬂow-consciouscode
  if(newCapacity-MAX_ARRAY_SIZE>0)
    newCapacity=hugeCapacity(minCapacity);
  queue=Arrays.copyOf(queue,newCapacity);
}
privatestaticinthugeCapacity(intminCapacity){
 if(minCapacity<0)//overﬂow
    thrownewOutOfMemoryError();
  return(minCapacity>MAX_ARRAY_SIZE)?
    Integer.MAX_VALUE:
    MAX_ARRAY_SIZE;
}