PriorityQueue(优先级队列总结)_综合

一，概念

队列是一种先进先出(FIFO)的数据结构，但有些情况下，操作的数据可能带有优先级，一般出队列时，可能需要优先级高的元素先出队列

数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)

二，PriorityQueue的特性

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

三，使用时的注意事项

1. 使用时必须导入PriorityQueue所在的包
import java.util.PriorityQueue;
2. PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出ClassCastException异常

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

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

5. 插入和删除元素的时间复杂度为 $\log_{2}N$

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

7. PriorityQueue默认情况下是小堆---即每次获取到的元素都是最小的元素

四，PriorityQueue的构造器（三种）

import java.util.PriorityQueue;public class MyPriorityQueue {public static void method1(){//不添加初始容量  默认为11PriorityQueue<Integer> p1 = new PriorityQueue<>();//添加初始容量为100PriorityQueue<Integer> p2 = new PriorityQueue<>(100);p1.offer(1);p1.offer(2);p1.offer(3);p1.offer(4);p1.offer(5);//使用集合容器来进行构造PriorityQueue<Integer> p3 = new PriorityQueue<>(p1);System.out.println(p3.peek());System.out.println(p3.size());}public static void main(String[] args) {method1();}
}

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

    public static void method2(){PriorityQueue<Integer> p1 = new PriorityQueue<>();p1.offer(10);p1.offer(12);p1.offer(14);p1.offer(16);p1.offer(18);System.out.println(p1.peek());PriorityQueue<Integer> p2 = new PriorityQueue<>(new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {return o2 - o1;}});p2.offer(10);p2.offer(12);p2.offer(14);p2.offer(16);p2.offer(18);System.out.println(p2.peek());}

五，插入/删除/获取优先级队列的元素以及使用

    public static void method3(){PriorityQueue<Integer> p = new PriorityQueue<>();p.offer(1);p.offer(2);p.offer(3);p.offer(4);p.offer(5);System.out.print(p.size() + " ");System.out.println(p.peek());p.poll();p.poll();System.out.print(p.size() + " ");System.out.println(p.peek());p.poll();p.poll();p.poll();System.out.print(p.size() + " ");System.out.print(p.peek() + " ");System.out.println(p.poll() + " ");if (p.isEmpty()){System.out.println("p is empty!");}else{System.out.println("p is not empty!");}}

六，堆

1.什么是堆

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

堆中某个节点的值总是不大于或不小于其父节点的值；

堆总是一棵完全二叉树

2.堆的存储方式

堆是一棵完全二叉树，因此可以层序的规则采用顺序的方式来高效存储，
注意：对于非完全二叉树，则不适合使用顺序方式进行存储，因为为了能够还原二叉树，空间中须要存储空节点，就会导致空间利用率比较低

将元素存储到数组中后，可以根据二叉树章节的性质5对树进行还原。假设i为节点在数组中的下标，则有：

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

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

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

3.堆的创建

向下调整

    public void shiftDown(int[] array,int parent){int child = parent * 2 + 1;int size = array.length;while(child < size){if ((child + 1 < size) && (array[child + 1] < array[child])){child = child + 1;}if (array[parent] <= array[child]){break;}else{int temp = array[parent];array[parent] = array[child];array[child] = temp;parent = child;child = parent * 2 + 1;}}for (int i = 0; i < array.length; i++) {System.out.print(array[i] + " ");}}

堆的创建

    //堆的创建public void createHeap(int[] array){int root = ((array.length - 2) >> 1);for (int i = root; i >= 0 ; i--) {shiftDown(array,root);}}

堆的插入与删除

向上调整

    public void shiftUp(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) / 1;}}}