数据结构：优先级队列— PriorityQueue
目录
一、PriorityQueue
二、PriorityQueue的构造方法
1、不带参数
2、带参数
3、用一个集合来创建
4、创建比较器
三、PriorityQueue的操作方法
1、boolean offer(E e)插入
2、E peek()获取
3、E pool()删除
4、int size()长度
5、void clear（）清空
6、Boolean isEmpty()判空
四、堆的应用
1、PriorityQueue的实现
2、堆排序
五、Top-k问题
（1）直接排序
（2）利用PriorityQueue进行升序排序
（3）Top-k算法
一、PriorityQueue
在Java中自带了一种优先级队列：PriorityQueue，它保证了每次取出的元素都是队列中最小或最大的，并且他的形态采用树形结构，通过实现一个完全二叉树的最小堆或最大堆来实现队列的排序。
注意事项：
- PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出 ClassCastException异常
- 不能插入null对象，否则会抛出NullPointerException
- 没有容量限制，可以插入任意多个元素，其内部可以自动扩容
- 插入和删除元素的时间复杂度为O(logn)
- PriorityQueue底层使用了堆数据结构
- PriorityQueue默认情况下是小堆---即每次获取到的元素都是最小的元素
二、PriorityQueue的构造方法
1、不带参数 PriorityQueue<>()
创建⼀个空的优先级队列，底层默认容量是11
PriorityQueue<Integer> q1 = new PriorityQueue<>();2、带参数 PriorityQueue<>(int initialCapacity)
创建⼀个空的优先级队列，底层的容量为initialCapacity
PriorityQueue<Integer> q2 = new PriorityQueue<>(100);
此时底层容量为100注意：此时initialCapacity的值不能小于1，否则就会抛出illegalArgumentException异常
3、用一个集合来创建 PriorityQueue(Collection<? extends E> c）
⽤ArrayList对象来构造⼀个优先级队列的对象
ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
q3中已经包含了三个元素
PriorityQueue<Integer> q3 = new PriorityQueue<>(list);
4、创建比较器
注意：默认情况下，PriorityQueue队列是小堆，如果需要大堆需要用户提供比较器
我们可以自己定义的比较器：直接实现 Comparator 接口，然后重写该接口中的 compare 方法即可
class ImBig implements Comparator<Integer> {
public int compare(Integer o1,Integer o2){
return o2.compareTo(o1);
//Byte,Double,Integer,Float,Long或Short类型的参数可以利用compareTo方法进行比较，
//大于返回1，等于返回0，小于返回-1
//return o2-o1;
//当然我们也可以返回两个数的差值o2-o1,当然如果我们传入的两个参数是ListNodee类型的，
//我们就不能使用compareTo方法,而是使用差值来比较
}
}
public static void main(String[] args) {
PriorityQueue<Integer> queue = new PriorityQueue<>(new ImBig());
queue.offer(1);
queue.offer(-1);
queue.offer(6);
System.out.println(queue.poll());
}此时我们来删除我们的第一个元素由于实现的是大根堆，此时要删除的元素应该为我们的大根堆的根结点即最大的元素6。
默认情况下，PriorityQueue队列是小堆，那么我们不实现比较器，我们删除的应该是我们的最小的元素-1.
但是有的情况下我们可能还是需要创立小堆的比较器
class ImLess implements Comparator<Integer>{
public int compare(Integer o1,Integer o2){
return o1.compareTo(o2);
//return o1-o2;
}
}三、PriorityQueue的操作方法
1、boolean offer(E e)插入
插入元素e，插入成功返回true，如果e对象为空，抛出NullPointerException异常，时间复杂度 O(logn)
注意：空间不够时候会自主扩容
在上面其实我们已经使用了，大小根堆的插入
注意：在插入的过程中可能会超出他的默认容量，但是PriorityQueue会自动扩容，他的扩容机制是：
- 如果容量小于64时，是按照oldCapacity（原来空间）的2倍方式扩容的
- 如果容量大于等于64，是按照oldCapacity（原来空间）的1.5倍方式扩容的
- 如果容量超过MAX_ARRAY_SIZE，按照MAX_ARRAY_SIZE来进行扩容
2、E peek()获取
获取优先级最高（堆顶）的元素，如果为空，返回null
获取大根堆的堆顶元素：
获取小根堆的堆顶元素：
3、E pool()删除
移除优先级最高的元素并返回，如果为空，返回null。
如果我们此时删除大根堆的堆顶元素，我们进行打印就会的到要删除的堆顶元素，此时我们在查询堆顶元素就不是原来的值了，而peek并不会删除。
4、int size()长度
他得到的长度是获取的有效元素个数
5、void clear（）清空
此时他会清空队列中的所有元素，此时队列的有效长度应为0
6、Boolean isEmpty()判空
检测堆是否为空，空返回true，不为空返回false
四、堆的应用
1、PriorityQueue的实现
PriorityQueue的实现是用堆作为底层结构封装优先级队列，因此PriorityQueue的大小根堆是根据堆排序来实现的。
2、堆排序
堆排序即利用堆的思想来进行排序，总共分为两个步骤：
（1）建堆
- 升序：建大堆
- 降序：建小堆
（2）利用堆删除思想来进行排序
我们以升序来举例，首先我们先建立一个大根堆，我们将大根堆的第一个元素（即最大的的元素）和最后一个元素进行交换，然后我们将交换后的第一个元素进行向下调整，要注意的是我们此时调整的范围是交换完后第一个元素到交换完后最后一个元素之前，调整完后，再让第一个元素个新的最后一个元素进行交换，直到最后一个元素的位置和第一个元素位置重合。接下来我们来看以下我们的过程图：
同理，降序就是创建一个小根堆进行调整
完整代码
//创建一个大根堆
public void createHeap(){
for(int parent = (usesize-1-1)/2;parent >=0 ;parent--){
sifDown(parent,usesize);
}
}
//向下调整
public void sifDown(int parent,int usesize){
int child = 2*parent + 1;
while(child < usesize){//孩子的位置是小于我们所给的长度的
if(child+1 < usesize && elem[child] < elem[child+1]){
child++;
}
if(elem[child] > elem[parent]){
swap(child,parent);
parent = child;
child = 2*parent + 1;
}else{
break;
}
}
}
//堆排序
public void Heapsort(){
int end = usesize-1;//end的下标为有效长度减一
while(end > 0){//不重合就进行调整
swap(0,end);//交换
sifDown(0,end);//调整
end--;//改变end的位置
//注意这里先交换后改变end，是因为在调整过程整孩子的位置是小于我们所给的长度的
}
}五、Top-k问题
Top-k问题：最小k个数
这个问题就是让我们求前k个最小的元素，对于这道题其实我们有三种解题方法
（1）直接排序
第一种，也是最简单的方法，直接将数组进行排序，找到前k个元素并打印打印
（2）利用PriorityQueue进行升序排序
原理：就是上面所讲的将他建立成一个大根堆然后利用堆排序进行升序排序，实际上就是直接向PriorityQueue中传值，然后打印前k个
public int[] smallestK(int[] arr, int k) {
PriorityQueue<Integer> queue = new PriorityQueue<>();
for(int i = 0;i < arr.length;i++){
queue.offer(arr[i]);
}
int[] ret = new int[k];
for(int j = 0;j < k;j++){
ret[j] = queue.poll();
}
return ret;
}（3）Top-k算法
我们建立前k个大根堆，之后将N-k个元素与堆顶元素进行比较，如果比堆顶元素小，就弹出堆顶元素，然后将这个小的元素入堆，然后对堆进行调整，之后再重复上述过程，直到将所有元素比完，最后弹出前K个元素。
过程图：
class ImBig1 implements Comparator<Integer>{
public int compare(Integer o1,Integer o2){
return o2.compareTo(o1);
}
}
class Solution {
public int[] smallestK(int[] arr, int k) {
int[] ret = new int[k];
if(arr.length <k || k <= 0){
return ret;
}
PriorityQueue<Integer> queue = new PriorityQueue<>(new ImBig1());
for(int i = 0;i<k;i++){
queue.offer(arr[i]);
}
for(int j = k;j < arr.length;j++){
int tmp = queue.peek();
if(tmp > arr[j]){
queue.poll();
queue.offer(arr[j]);
}
}
for(int i = 0;i < k;i++ ){
ret[i] = queue.poll();
}
return ret;
}
}好了，今天的分享就到这里了，还请大家多多关注，我们下一篇见！