优先级队列（PriorityQueue）

优先级队列的概念

我们都知道队列是一种先进先出（FIFO）的数据结构，但有些情况下，操作的数据可能带有优先级，一般出队列时可能需要优先级高的元素出队列，此时队列就显得不合适了。因此我们引入优先级队列(PriorityQueue)
该数据结构应提供两个基本操作：
1.返回最高优先级对象
2.添加新的对象

在集合框架中所处的位置

java集合中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列，PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的

优先级队列的特性

1.注意的点

1.使用时必须导入PriorityQueue所在的包，即：

import java.util.PriorityQueue;

2.PriorityQueue中放置元素必须能够比较大小，不能插入无法比较大小的对象，否则会抛出异常
3.不能插入null对象，否则会抛出NullPointerException
4.没有容量限制，可以插入任意多个元素，其内部可以自动扩容

当容量小于64时，按照 oldCapacity 的 2 倍方式扩容；
当容量大于等于64，按照 oldCapacity 的1.5倍方式扩容；
当容量超过 MAX_ARRAY_SIZE，按照MAX_ARRAY_SIZE 进行扩容；

jdk1.8 中，PriorityQueue的扩容方式：

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;    private void grow(int minCapacity) {        int oldCapacity = queue.length;                int newCapacity = oldCapacity + ((oldCapacity < 64) ? (oldCapacity + 2): (oldCapacity >> 1));        if (newCapacity - MAX_ARRAY_SIZE > 0) {            newCapacity = hugeCapacity(minCapacity);        }        queue = Arrays.copyOf(queue,newCapacity);    }

5.插入和删除元素的时间复杂度为O(log₂N)
6.PriorityQueue底层使用了堆数据结构
7.PriorityQueue默认情况下是小堆——即每次获取到的元素都是最小的

如果想要创建大堆，则需要构造比较器——实质：实现 Comparator 接口，重写该接口中的 compare 方法

大堆创建代码如下：

//用户自己定义的比较器：直接实现Comparator接口，然后重写该接口中compare方法即可import java.util.Comparator;public class IntCmp implements Comparator<Integer> {    @Override    public int compare(Integer o1, Integer o2) {        return o2-o1; //o1-o2就是小堆}}

import java.util.PriorityQueue;public class TestPriorityQueue {    public static void main(String[] args) {        PriorityQueue<Integer> q = new PriorityQueue<>(new IntCmp());        q.offer(1);        q.offer(2);        q.offer(5);        q.offer(3);        System.out.println(q.peek());  //5    }}

也可以写成这样：

import java.util.PriorityQueue;import java.util.Comparator;public class TestPriorityQueue {    public static void main(String[] args) {        PriorityQueue<Integer> q = new PriorityQueue<>(new Comparator<Integer>() {            @Override            public int compare(Integer o1, Integer o2) {                return o2 - o1; //o1-o2就是小堆            }        });        q.offer(1);        q.offer(2);        q.offer(5);        q.offer(3);        System.out.println(q.peek());  //5    }}

2.三种构造方法

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

测试代码如下：

import java.util.PriorityQueue;public class TestPriorityQueue {    public static void method(){        int[] arr = {4,1,9,2,3,6,7,8,5};        PriorityQueue<Integer> q=new PriorityQueue<>(arr.length);        for(int e:arr) {            q.offer(e);        }        System.out.println(q.size());  //9        System.out.println(q.peek());  //1        q.poll();        q.poll();        System.out.println(q.size()); //7        System.out.println(q.peek()); //3        q.clear();        if(q.isEmpty()){            System.out.println("优先级队列为空");        }else{            System.out.println("优先级队列不为空");        }    }    public static void main(String[] args) {        method();    }}

优先级队列的模拟实现

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

1.堆的概念

n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时，称之为堆。
(k_i ≤ k_2i且k_i ≤ k_2i+1)或者(k_i ≥ k_2i且k_i ≥ k_2i+1)，若将和此次序列对应的一维数组（即以一维数组作此序列的存储结构）看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不大于（或不小于）其左、右孩子结点的值。由此，若序列{k1,k2,…,kn}是堆，则堆顶元素（或完全二叉树的根）必为序列中n个元素的最小值（或最大值）
（摘自百度百科）
总之：将根节点最大的堆叫大堆，将根节点最小的堆叫小堆

• 堆中某个结点的值总是不大于或不小于其父结点的值
• 堆总是一棵完全二叉树。

2.堆的存储方式

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

注：对于非完全二叉树，则不适合使用顺序方式进行存储，因为为了能够还原二叉树，空间中必须要存储空结点，就会导致空间利用率比较低

2.堆的创建

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

不难发现：根结点的左右子树均已满足堆的性质（除根结点外，其余结点均是小于其孩子结点的），
如下图所示：

因此，只需要将根结点向下调整到合适位置即可创建一个小堆；
向下调整步骤：

• a.让 parent 标记需要调整的结点，child 标记其左孩子的结点（ 注意：parent如果有孩子一定先是有左孩子）
• b.如果左孩子存在时，即：（child   （1）parent右孩子是否存在，存在将左右孩子进行比较，让child 标记出找出的较小的那个孩子；
    （2）将parent与较小的那个孩子进行比较，当 parent>child
  标记的孩子时，就进行交换；但交换可能就会导致下面子树不满足堆的特性，因此，需要更新变量（parent=child，child=parent*2+1），继续
  b 操作，

注意：

在将某结点往下调整时，必须保证该结点的左右子树均满足堆的特性，才能使用；
代码如下：

 public void shiftDown(int[] array){        int parent=0;        int child=2*parent+1; //child来标记左孩子        int size=array.length;        while(child<size){          // 右孩子存在时，找左右孩子中较小的孩子,用child进行标记         if(child+1 < size && array[child+1] < array[child]){                child += 1;            }            // 如果双亲比其最小的孩子还小，说明该结构已经满足堆的特性了            if (array[parent] <= array[child]) {                break;            }else{                //将双亲与较小的孩子进行交换                int temp=array[parent];                array[parent]=array[child];                array[child]=temp;                // 当parent中大的元素往下移动时，可能会造成子树不满足堆的性质，因此需要继续向下调整                parent = child;                child = parent * 2 + 1;            }        }    }     public static void main(String[] args) {        int[] array={27,15,19,18,28,34,65,49,25,37};        shiftDown(array);     }}

对于以上属于特殊情况，如遇到左右子树不满足堆特性的情况该如何处理？
任意序列建堆:

• （1）找到当前树中的倒数第一个非叶子结点，该结点也是最后一个结点的双亲所在的位置，而最后一个结点的位置下标为 size-1；
  其双亲的下标为：（(size-1）-1)/2；
• （2）从该非叶子结点开始往回倒，直到根的位置，遇到一个结点，就以该结点为二叉树进行向下调整；

代码如下：

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

3.堆的插入

堆的插入有两个步骤：
  （1）先将元素放入底层空间中（注意：空间不够时需要扩容）
  （2）将最后新插入的结点向上调整，直到满足堆的性质

public void offer(int e){            array[size]=e;            size++;   //将插入的新元素向上调整            shiftUp(array,size-1);        }

3.堆的删除

  （1）将堆顶元素与堆中最后一个元素进行交换
  （2）将堆中有效数据的个数减少一个
  （3） 对堆顶元素进行向下调整

public Integer poll(){           int ret=array[0];           //将堆顶元素与最后一个元素交换            array[0]=array[size-1];            //堆中有效元素个数减少一个             size--;             //将堆顶元素使用向下调整到合适位置             shiftDown(array,size,0);             return ret;        }

4.获取堆顶元素

public int peek(){   return array[0];}

以上就是本次的全部内容~~