优先级队列简介
PriorityQueue，即优先级队列。它可以保证每次出出来的数据是队列中最大或最小的元素。
JDK1.8中的PriorityQueue底层使用了堆这种数据结构。
关于堆
堆实际就是在完全二叉树的基础上进行了一些调整。
堆的性质：
堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树。
为什么得用完全二叉树
我们来看下图就明白了:
首先我们得明白,堆中数据的存储是用数组来实现的,那么它们的存储结构就出来了:
我们可以看到对于完全二叉树,它可以做到不浪费空间,而非完全二叉树可能会产生很多零碎的空间浪费了,因此我们采用完全二叉树.
将元素存储到数组中后，可以根据二叉树的性质对树进行还原。
假设 i 为节点在数组中的下标，则有：
如果i为0，则i表示的节点为根节点，否则i节点的双亲节点为 (i - 1)/2
如果2 * i + 1 小于总的节点个数，则节点i的左孩子下标为2 * i + 1，否则没有左孩子
如果2 * i + 2 小于总的节点个数，则节点i的右孩子下标为2 * i + 2，否则没有右孩子
用堆来实现优先级队列
先来看看优先级队列的常用方法
插入/删除/获取优先级最高的元素
1.boolean offer(E e)
插入元素e，插入成功返回true，如果e对象为空，抛出NullPointerException异常，时间复杂度 ，注意：空间不够时候会进行扩容
2.E peek()
获取优先级最高的元素，如果优先级队列为空，返回null
3.E poll()
移除优先级最高的元素并返回，如果优先级队列为空，返回null
4.int size()
获取有效元素的个数
5.void clear()
清空
6.boolean isEmpty()
检测优先级队列是否为空，空返回true
模拟实现
public class PriorityQueue { public int[] elem; public int usedSize; //记录元素个数 public PriorityQueue() { elem = new int[11]; //数组初始大小为11 usedSize = 0; } /** * 建堆的时间复杂度：O(n*logn) * * @param array */ public void createHeap(int[] array) { //将该数组变为优先级队列 elem = array; usedSize = array.length; for(int i = (usedSize-2)/2; i >= 0; i--) { //从最后一个元素的父节点开始依次向下调整 shiftDown(i,usedSize); } } /** * * @param root 是每棵子树的根节点的下标 * @param len 是每棵子树调整结束的结束条件 * 向下调整的时间复杂度：O(logn) */ private void shiftDown(int root,int len) { int a = root*2 + 1; //a表示左边的子节点 while(a < len) { //向下调整直到a越界了 if(a+1 < len && elem[a] < elem[a+1]) { //如果root有右节点,并且右节点大于左节点,则令a等于右节点 a = a+1; //这里a就表示root的最大子节点 } if(elem[root] < elem[a]) { //如果最大子节点大于root节点,则两者交换 int tmp = elem[a]; elem[a] = elem[root]; elem[root] = tmp; root = a; //将root指向交换了的子节点 a = root*2 + 1; //a重新指向root的左子节的 }else { break; //不大于直接退出循环 } } } /** * 入队：仍然要保持是大根堆 * @param val */ public void push(int val) { if(isFull()) { //如果满了扩容 elem = Arrays.copyOf(elem,2*elem.length); } elem[usedSize++] = val; //将待添加的元素放在数组最后面 shiftUp(usedSize-1); //将添加的元素进行向上调整 } private void shiftUp(int child) { int root = (child-1) / 2; //找出child的父节点root while(root >= 0) { if(elem[child] > elem[root]) { //如果子节点大于父节点,则交换 int tmp = elem[child]; elem[child] = elem[root]; elem[root] = tmp; child = root; //将子节点指向父节点 root = (child-1) / 2; }else { break; } } } public boolean isFull() { return usedSize == elem.length; } /** * 出队【删除】：每次删除的都是优先级高的元素 * 仍然要保持是大根堆 */ public void pollHeap() { if(isEmpty()) { throw new RuntimeException("队列为空,无法删除元素"); } elem[0] = elem[--usedSize]; //删除其实就是将最后一个元素覆盖第一个元素 shiftDown(0,usedSize); //然后对第一个元素进行向下调整 } public boolean isEmpty() { return usedSize == 0; } /** * 获取堆顶元素 * @return */ public int peekHeap() { return elem[0]; } }
这里实现的是大根堆, 其实PriorityQueue底层是小根堆.
使用PriorityQueue的注意事项
1.使用时必须导入PriorityQueue所在的包，即：
import java.util.PriorityQueue;
2.PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出
ClassCastException异常.
3.不能插入null对象，否则会抛出NullPointerException
4.插入元素时, 若空间不足, 其内部可以自动扩容
可以看到, 如果原数组大小小于64, 则二倍扩容, 大于则1.5倍扩容.
可以看到扩容最大为 Integer.MAX_VALUE 也就是2^31 - 1.
5.插入和删除元素的时间复杂度为: O(logN)
6.PriorityQueue底层使用了堆数据结构
7.PriorityQueue默认情况下是小堆—即每次获取到的元素都是最小的元素.
PriorityQueue常用接口
优先级队列的构造方法
可以看到有很多构造方法:
这里介绍几个我们常用的构造方法:
默认情况下，PriorityQueue队列是小堆，如果需要大堆需要用户提供比较器.
用到这个构造方法:
// 用户自己定义的比较器：直接实现Comparator接口，然后重写该接口中的compare方法即可 class IntCmp implements Comparator<Integer>{ @Override public int compare(Integer o1, Integer o2) { return o2-o1; //这里如果是o1-o2则是小根堆 } } public class TestPriorityQueue { 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()); } }
