前言
想要看如何使用可以通过目录跳转到 PriorityQueue的使用
优先级队列
概念
队列是一种先进先出(FIFO)的数据结构，但有些情况下，操作的数据可能带有优先级，一般出队
列时，可能需要优先级高的元素先出队列，该中场景下，使用队列显然不合适
比如：在手机上玩游戏的时候，如果有来电，那么系统应该优先处理打进来的电话；初中班主任排座位时可能会让成绩好的同学优先挑选座位。
堆
为什么要讲推
我们可能在疑惑,不是优先级队列吗,跟堆有什么关系?
那是因为: JDK1.8中的PriorityQueue底层使用了堆这种数据结构，而堆实际就是在完全二叉树的基础上进行了一些调整
概念
堆的存储
从堆的概念可知，堆是一棵完全二叉树，因此可以层序的规则采用顺序的方式来高效存储
注意：对于非完全二叉树，则不适合使用顺序方式进行存储，因为为了能够还原二叉树，空间中必须要存储空节点，就会导致空间利用率比较低
PriorityQueue的使用
优先级队列的构造方法
import java.util.PriorityQueue;
static void TestPriorityQueue(){
//1. 创建一个空的优先级队列，底层默认容量是11
PriorityQueue<Integer> q1 = new PriorityQueue<>();
//2. 创建一个空的优先级队列，底层的容量为initialCapacity
PriorityQueue<Integer> q2 = new PriorityQueue<>(100);
ArrayList<Integer> list = new ArrayList<>();
list.add(4);
list.add(3);
list.add(2);
list.add(1);
//3. 用ArrayList对象来构造一个优先级队列的对象
// q3中已经包含了三个元素
PriorityQueue<Integer> q3 = new PriorityQueue<>(list);
System.out.println(q3.size());//打印有几个元素
System.out.println(q3.peek());//打印头一个元素(不弹出)
}注意：默认情况下，PriorityQueue队列是小根堆，如果需要大根堆需要用户提供比较器
// 用户自己定义的比较器：直接实现Comparator接口，然后重写该接口中的compare方法即可
class IntCmp implements Comparator<Integer>{
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
}
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);
}
优先级队列的常用方法
static void TestPriorityQueue2(){
int[] arr = {4,1,9,2,8,0,7,3,6,5};
// 一般在创建优先级队列对象时，如果知道元素个数，建议就直接将底层容量给好
// 否则在插入时需要不多的扩容
// 扩容机制：开辟更大的空间，拷贝元素，这样效率会比较低
PriorityQueue<Integer> q = new PriorityQueue<>(arr.length);
for (int e: arr) {
q.offer(e);
}
System.out.println(q.size()); // 打印优先级队列中有效元素个数
System.out.println(q.peek()); // 获取优先级最高的元素
// 从优先级队列中删除两个元素之后，再次获取优先级最高的元素
q.poll();
q.poll();
System.out.println(q.size()); // 打印优先级队列中有效元素个数
System.out.println(q.peek()); // 获取优先级最高的元素
q.offer(0);
System.out.println(q.peek()); // 获取优先级最高的元素
// 将优先级队列中的有效元素删除掉，检测其是否为空
q.clear();
if(q.isEmpty()){
System.out.println("优先级队列已经为空!!!");
} else{
System.out.println("优先级队列不为空");
}
}注意事项
关于PriorityQueue的使用要注意：
1. 使用时必须导入PriorityQueue所在的包，即：
import java.util.PriorityQueue;
2. PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出
ClassCastException异常
3. 不能插入null对象，否则会抛出NullPointerException
4. 没有容量限制，可以插入任意多个元素，其内部可以自动扩容
5. 插入和删除元素的时间复杂度为
6. PriorityQueue底层使用了堆数据结构
7. PriorityQueue默认情况下是小堆---即每次获取到的元素都是最小的元素
把自己定义的类存入PriorityQueue
class Student implements Comparable<Student>{
public int num;//学号
public int age;//年龄
public String name;//姓名
public Student(int num, int age, String name) {
this.num = num;
this.age = age;
this.name = name;
}
//我们重写比较器,用年龄进行比较
@Override
public int compareTo(Student o) {//需要在自己的类中 重写比较器,这样自己的类才能比较
return this.age - o.age;
}
@Override
public String toString() {
return "Student{" +
"name='" + name + '\'' +
'}';
}
}
public class Main {
public static void main(String[] args) {
PriorityQueue<Student> students = new PriorityQueue<>();
Student s1 = new Student(123,12,"老二");
Student s2 = new Student(222,8,"老三");
Student s3 = new Student(333,19,"老大");
students.offer(s1);
students.offer(s2);
students.offer(s3);
while (!students.isEmpty()) {
System.out.println(students.poll());
}
//输出结果:
//Student{name='老三'}
//Student{name='老二'}
//Student{name='老大'}
}
}
