我们知道,Queue是一个先进先出(FIFO)的队列。
在很多应用中,我们通常需要按照优先情况对待处理对象进行处理,比如首先处理优先级最高的对象,然后处理次高的对象。最简单的一个例子就是,在手机上玩游戏时,如果有来电,那么系统应该优先处理进来的电话。
这个时候,我们发现,要实现上述的操作,用Queue就不行了,因为Queue会严格按 FIFO 的原则取出队首元素。故有了我们需要的优先队列:PriorityQueue。
Java 中 PriorityQueue 继承了 Queue 接口,它的底层是一个堆。
- PriorityQueue 的底层是一个数组
- 我们可以转到它的定义,可以看到它的底层定义是一个数组。为了知道这个数组的初始大小有多大
- 再通过它的参构造方法转到定义,又可以看到
- 再点击 this,转到其定义,我们发现又跳到了一个含两个参数的构造方法
- 又在 PriorityQueue 的定义中 DEFAULT_INITIAL_CAPACITY = 11,即 initialCapacity = 11,所以我们可以知道数组的初始大小为11
- <p>PriorityQueue 的底层默认是一个小根堆</p>
- <p>如何使 PriorityQueue 的底层是一个大根堆?</p>
- 引用上图 PriorityQueue 的含参定义,我们知道第一个参数代表数组的大小,而第二个参数就一个比较器,传给他的就是比较的方法,通过给他传入大根堆的比较方式,我们就可以使 PriorityQueue 的底层变成大根堆
![]()
注意: 下面的示例都是一份代码分开拿出来的,上下其实是有逻辑关系的
示例一: 用 Priority Queue 创建一个优先级队列
PriorityQueue<Integer> queue=new PriorityQueue<>();
示例二: 入队列
queue.offer(10); queue.offer(2); queue.offer(5);
示例三: 得到队首元素
System.out.println(queue.peek()); // 结果为:2
示例四: 出队列
System.out.println(queue.poll()); // 结果为:2
示例五: 返回集合中元素个数
System.out.println(queue.size()); // 结果为:2
当我们使用优先级队列的时候,插入元素其实有个前提:
插入的元素不能是 null 或者元素之间必须能够进行比较
而基本的包装类类型都可以进行比较,如:Integer、Double、Float。但是对于我们自定义的类型,其实就可能不能比较,就如下面这个类当我们使用优先级队列对它的对象进行插入时,其实会报错
class Student{ private String name; private int age; public Student(String name, int age, double score) { this.name = name; this.age = age; } } public class TestDemo{ public static void main(String[] args){ PriorityQueue<Student> queue=new PriorityQueue<>(); queue.offer(new Student("Tom",18)); queue.offer(new Student("Hen",34)); } }
这是因为优先级队列的底层默认是一个小根堆,它存入元素时是需要进行比较对象的大小的。
我们可以转到 PriorityQueue 的无参构造方法的定义看看
此时我们的 comparator 默认是 null,我们再转到 offer 方法的定义看看
好像并没有什么异常,但是由于我插入第二个元素时,i 不为0,所以要进行 siftUp 方法,我们转到它的定义
由于我们知道 comparator 为 null,那么则要进行 siftUpComparable 方法,继续转到它的定义
我们发现,创建的 Student 的对象,被强转为了 Comparable<? super E>,并且还调用了 compareTo 方法。如果大家有看过我写的 解析 Java 的多态、抽象类和接口 和 Java 对象的比较 这两篇文章,那我就有讲到 compareTo 这个方法。这个方法是 Comparable 的一个抽象方法,定义的是比较对象大小的一个规则。
因此为了解决这个问题,我们就可以使用和 Comparable 或 Comparator 接口相关的知识
6.1 思路
这里便不对源码做具体分析,我们如果要 PriorityQueue 创建出的是一个大根堆,只需要对具体类型写一个比较器即可
6.2 代码实现
// 定义的某个要比较类型的比较器 class IntegerComparator implements Comparator<Integer>{ @Override public int compare(Integer o1,Integer o2){ // 如果第二个元素-第一个元素就是大根堆的实现方式,反之则为小根堆的创建方式,可以从源码去了解 return o2-o1; } } public class TestDemo{ public static void main(String[] args){ PriorityQueue<Integer> maxHeap=new PriorityQueue<>(IntegerComparator); } }
6.3 使用匿名内部类
上述代码也可以写成
public class TestDemo{ public static void main(String[] args){ PriorityQueue<Integer> maxHeap=new PriorityQueue<>(new Comparator<Integer>(){ @Override public int compare(Integer o1,Integer o2){ return o2-o1; } }) } }
这相当使用了一个匿名的内部类的方式去创建大根堆
本文为互联网自动采集或经作者授权后发布,本文观点不代表立场,若侵权下架请联系我们删帖处理!文章出自:https://t4dmw.blog.csdn.net/article/details/121210232