Java数据结构之优先级队列(PriorityQueue)用法详解
概念
优先级队列是一种先进先出（FIFO）的数据结构，与队列不同的是，操作的数据带有优先级，通俗的讲就是可以比较大小，在出队列的时候往往需要优先级最高或者最低的元素先出队列，这种数据结构就是优先级队列（PriorityQueue）
PriorityQueue的使用
构造方法
这里只介绍三种常用的构造方法
| 构造方法 | 说明 |
| PriorityQueue() | 不带参数，默认容量为11 |
| PriorityQueue(int initialCapacity) | 参数为初始容量，该初始容量不能小于1 |
| PriorityQueue(Collection<? extends E> c) | 参数为一个集合 |
代码展示：
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
public class TestPriorityQueue {
public static void main(String[] args) {
PriorityQueue<Integer> p1 = new PriorityQueue<>(); //容量默认为11
PriorityQueue<Integer> p2 = new PriorityQueue<>(10); //参数为初始容量
List<Integer> list = new ArrayList<>();
list.add(0);
list.add(1);
list.add(2);
PriorityQueue<Integer> p3 = new PriorityQueue<>(list); //使用集合list作为参数构造优先
// 级队列
}
}
常用方法
| 方法 | 说明 |
| boolean offer(E e) | 插入元素e，返回是否插入成功，e为null，会抛异常 |
| E peek() | 获取堆（后面介绍堆）顶元素，如果队列为空，返回null |
| E poll() | 删除堆顶元素并返回，如果队列为空，返回null |
| int size() | 获取有效元素个数 |
| void clear() | 清空队列 |
| boolean isEmpty() | 判断队列是否为空 |
offer方法的测试
PriorityQueue<Integer> p = new PriorityQueue<>();
p.offer(1);
p.offer(2);
p.offer(3);
System.out.println(p.size());
p.offer(null);
打印结果：
1，2，3都正常插入，但是插入null的时候，报了NullPointerException空指针异常
peek与poll方法的测试
PriorityQueue<Integer> p = new PriorityQueue<>();
p.offer(1);
p.offer(2);
p.offer(3);
System.out.println(p.peek());
System.out.println(p.poll());
System.out.println(p.size());
p.clear();
System.out.println(p.peek());
System.out.println(p.poll());
打印结果：
默认是小堆，所以堆顶元素是1，获取到1，在删除1，剩余元素个数为两个，当队列为空的时候，这两个方法都返回null
size，isEmpty，clear方法的测试
PriorityQueue<Integer> p = new PriorityQueue<>();
p.offer(1);
p.offer(2);
p.offer(3);
System.out.println(p.size());
System.out.println(p.isEmpty());
p.clear();
System.out.println(p.isEmpty());
打印结果：
打印元素个数为3，所以不为空输出false，清空后，队列为空，输出true
注意事项
PriorityQueue中存放的元素必须能比较大小，不能比较大小的对象不能插入，会抛出ClassCastException异常
例如：向优先级队列中插入两个学生类型的数据
class Student {
private String name;
private int age;
public Student(String name, int age) {
this.name = name;
this.age = age;
}
}
public class Test {
public static void main(String[] args) {
Student s1 = new Student("张三",25);
Student s2 = new Student("李四",30);
PriorityQueue<Student> p = new PriorityQueue();
p.offer(s1);
p.offer(s2);
}
}
结果：报了类型转换异常的错误，因为student类型不能直接比较大小
如果想比较两个自定类型的大小，请参考Java中对象的比较这篇文章
- 不能插入null对象，否则会抛NullPointerException异常
- 内部可以自动扩容
- PriorityQueue底层使用堆数据结构
- PriorityQueue默认是小堆，如果想要创建大堆可以使用如下方式创建：
PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
});
注意：o2-o1是创建大堆，o1-o2是创建小堆
PriorityQueue的扩容方式
以下是JDK1.8中扩容的方式：
说明：
- 如果容量小于64，按照oldCapacity的2倍扩容
- 如果容量大于等于64，按照oldCapacity的1.5倍扩容
- 如果容量超过MAX_ARRAY_SIZE，按照MAX_ARRAY_SIZE扩容
小试牛刀（最小k个数）
题目
方法：创建一个优先级队列，奖数组中的元素依次放入该优先级队列中，在依次从该优先级队列取出k个即可
class Solution {
public int[] smallestK(int[] arr, int k) {
int[] ret = new int[k];
if(k == 0 || arr.length==0){
return ret;
}
PriorityQueue<Integer> p = new PriorityQueue<>(arr.length);
for(int i = 0;i < arr.length;i++){
p.offer(arr[i]);
}
for(int i = 0;i < k;i++){
ret[i] = p.poll();
}
return ret;
}
}
堆的介绍
JDK1.8中PriorityQueue底层采用了堆数据结构，堆其实就是对完全二叉树的元素作出了一些调整
所谓堆就是将一组数据按照完全二叉树的顺序存储方式存储，保证每一个根结点元素大于它的孩子结点的元素（大根堆）或者小于它的孩子结点的元素（小根堆）
堆的性质
堆中某个结点的值总是不大于或着不小于其父节点的值
堆是一颗完全二叉树
堆的创建
此处我们创建小堆，以21，15，19，17，18，23，25为例
发现上述序列根的左右子树都已经满足小堆的特性，故只需要将根结点向下调整即可
向下调整的过程：
1. 用parent标记要被调整的结点，child标记parent的左孩子
2. 如果左孩子存在，即child<size,size为序列元素的个数，进行以下操作，直到左孩子不存在
- 判断parent右孩子是否存在，如果存在让child标记两个孩子最小的孩子
- 如果parent小于child，则将parent与child标记的元素交换位置，如果parent大于child，说明此时已经满足小堆的特性
- 让parent=child，child=parent*2+1，循环步骤2，直到不满足步骤2的条件
代码展示：
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]>array[child+1]){
child = child+1;
}
if(array[parent] > array[child]){
swap(array,parent,child);
parent = child;
child = parent*2+1;
}else {
break;
}
}
}
注意：在调整以parent为根的二叉树时，必须满足parent的左右子树满足堆的特性，此时才能向下调整parent
时间复杂度分析：最坏情况从根比到叶子，比较的次数为二叉树的高度，故时间复杂度为O(log2N)
那么对于普通的序列如1，5，3，8，7，6，即根节点的左右子树不满足大堆的特性，该如何调整？
方法：从倒数第一个非叶子结点开始调整，直到调整到根
代码展示：
public void createHeap(int[] array){
int root = (array.length-2)>>1;
for(;root>=0;root--){
shiftDown(array,root);
}
}
创建堆的时间复杂度
故建堆的时间复杂度为O(N)
堆的插入
堆的插入分为两步：
- 将元素插入队列尾部，如果空间不够需要扩容
- 将新插入的结点向上调整，直到满足堆的特性
例如：给大堆8，7，6，5，1，3插入9
代码展示：
public void shiftUp(int[] array,int child){
int parent = (child-1)/2;
while(child > 0){
if(array[child] < array[parent]){
break;
}else {
swap(array,parent,child);
child = parent;
parent = (child-1)/2;
}
}
}
堆的删除
堆删除的是堆顶元素
删除步骤：
- 交换堆顶与堆最后一个元素的位置
- 将堆中的有效元素个数减少一个
- 将堆顶元素向下调整
代码展示：
public int poll(){
int oldVal = array[0];
array[0] = array[array.length-1];
size--;
shiftDown(array,0);
return oldVal;
}
优先级队列的模拟实现
此处用小堆实现优先级队列，并且队列中保存的元素为Integer类型
准备工作包括：构造方法，向上调整，向下调整，交换
public class MyPriorityQueue {
Integer[] array;
int size;
public MyPriorityQueue(){
array = new Integer[11];
size = 0;
}
public MyPriorityQueue(int initCapacity){
if(initCapacity < 1){
throw new IllegalArgumentException("初始容量小于1");
}
array = new Integer[initCapacity];
size = 0;
}
public MyPriorityQueue(Integer[] arr){
array = new Integer[arr.length];
for(int i = 0;i < arr.length;i++){
array[i] = arr[i];
}
size = arr.length;
int lastLeafParent = (size-2)/2;
for(int root = lastLeafParent;root >= 0;root--){
shiftDown(root);
}
}
public void shiftDown(int parent){
int child = parent*2+1;
while(child < size){
if(child+1<size && array[child+1]<array[child]){
child = child+1;
}
if(array[parent] > array[child]){
swap(parent,child);
parent = child;
child = parent*2+1;
}else {
return;
}
}
}
public void shiftUp(int child){
int parent = (child-1)/2;
while(child > 0){
if(array[child] < array[parent]){
swap(child,parent);
child = parent;
parent = (child-1)/2;
}else {
return;
}
}
}
public void swap(int a,int b){
int t = array[a];
array[a] = array[b];
array[b] = t;
}
}
插入
public boolean offer(Integer e){
if(e == null){
throw new NullPointerException("插入的元素为null");
}
ensureCapacity();
array[size++] = e;
shiftUp(size-1);
return true;
}
private void ensureCapacity(){
if(array.length == size){
int newCapacity = array.length*2;
array = Arrays.copyOf(array,newCapacity);
}
}
注意：插入前需要判断是否扩容，此处扩容按照2倍方式扩容
删除
public Integer poll(){
if(isEmpty()){
return null;
}
Integer ret = array[0];
swap(0,size-1);
shiftDown(0);
return ret;
}
获取堆顶元素
public Integer peek(){
if(isEmpty()){
return null;
}
Integer ret = array[0];
return ret;
}
获取有效元素个数
public int size(){
return size;
}
判空
public boolean isEmpty(){
return size==0;
}
清空
public void clear(){
size = 0;
}
堆的应用
- PriorityQueue的实现，PriorityQueue底层采用堆数据结构实现的
- 堆排序，详见基本排序算法总结(Java实现)
- Top-k问题
Top-k问题
即求数据中前k个最大或者最小元素，一般情况下数据量都会比较大
如果数据量大使用排序那种方法就不可取了，那么如何解决呢？
1. 使用数据中前k个数据建堆
求前k个最大，建小堆
求前k个最小，建大堆
2. 用剩余的元素依次与堆顶元素比较
求前k个最大，若比堆顶元素大，则替换小堆堆顶元素
求前k个最小，若比堆顶元素小，则替换大堆堆顶元素
以上就是Java数据结构之优先级队列(PriorityQueue)用法详解的详细内容，更多关于Java优先级队列的资料请关注编程网其它相关文章！
免责声明：
① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的，并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据，供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。
② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
