1 前言
PriorityQueue是一种特殊的队列，满足队列的“队尾进、队头出”条件，但是每次插入或删除元素后，都对队列进行调整，使得队列始终构成最小堆（或最大堆）。具体调整如下：
- 插入元素后，从堆底到堆顶调整堆；
- 删除元素后，将队尾元素复制到队头，并从堆顶到堆底调整堆。
PriorityQueue采用数组实现，也是一棵完全二叉树，构成堆结构。数组初始大小为11。
Queue框架如下：
Queue框架
2 PriorityQueue常用方法
public boolean add(E e); //在队尾添加元素，并调整堆结构
public E remove(); //在队头删除元素，并返回，再调整堆结构
public E element(); //返回队头元素（不删除）
public boolean isEmpty(); //判断队列是否为空
public int size(); //获取队列中元素个数
public void clear(); //清空队列
public boolean contains(Object o); //判断队列中是否包含指定元素（从队头到队尾遍历）
public Iterator<E> iterator(); //迭代器
3 简单案例
3.1 最小优先队列
import java.util.PriorityQueue;
public class Main {
static int[] a={6,4,7,3,9,8,1,2,5,0};
public static void main(String[] args) {
fun();
}
static void fun() {
PriorityQueue<Integer> que=new PriorityQueue<Integer>();
for(int e:a) {
que.add(e);
}
for(int e:que) {
System.out.print(e+" ");
}
System.out.println();
while(!que.isEmpty()) {
int e=que.remove();
System.out.print(e+" ");
}
}
}
运行结果：
0 1 3 4 2 8 7 6 5 9
0 1 2 3 4 5 6 7 8 9
堆结构：
最小优先队列内部堆结构
3.2 最大优先队列
import java.util.Comparator;
import java.util.PriorityQueue;
public class Main {
static int[] a={6,4,7,3,9,8,1,2,5,0};
public static void main(String[] args) {
fun();
}
static void fun() {
PriorityQueue<Integer> que=new PriorityQueue<Integer>(new Comparator<Integer>() {
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
});
for(int e:a) {
que.add(e);
}
for(int e:que) {
System.out.print(e+" ");
}
System.out.println();
while(!que.isEmpty()) {
int e=que.remove();
System.out.print(e+" ");
}
}
}
运行结果：
9 7 8 5 4 6 1 2 3 0
9 8 7 6 5 4 3 2 1 0
堆结构：
最大优先队列内部堆结构
3.3 topK问题
topK问题是指：从海量数据中寻找最大的前k个数据，比如从1亿个数据中，寻找最大的1万个数。
使用优先队列，能够很好的解决这个问题。先使用前1万个数构建最小优先队列，以后每取一个数，都与队头元素进行比较，若大于队头元素，就将队头元素删除，并将该元素添加到优先队列中；若小于队头元素，则将该元素丢弃掉。如此往复，直至所有元素都访问完。最后优先队列中的1万个元素就是最大的1万个元素。
为方便实验，这里以求 {6,4,7,3,9,8,1,2,5,0} 中最大的5个数为例。
import java.util.PriorityQueue;
public class Main {
static int[] a={6,4,7,3,9,8,1,2,5,0};
public static void main(String[] args) {
fun();
}
static void fun() {
PriorityQueue<Integer> que=new PriorityQueue<Integer>();
for(int i=0;i<5;i++) {
que.add(a[i]);
}
for(int i=5;i<10;i++) {
if(a[i]>que.element()) {
que.remove();
que.add(a[i]);
}
}
while(!que.isEmpty()) {
int e=que.remove();
System.out.print(e+" ");
}
}
}
运行结果：
5 6 7 8 9