优先级队列
优先级队列是一种先进先出的数据结构，操作的数据带有优先级，这种数据结构就是优先级队列（PriorityQueue），优先级队列是一种先进先出（FIFO）的数据结构，与队列不同的是，操作的数据带有优先级，通俗的讲就是可以比较大小，在出队列的时候往往需要优先级最高或者最低的元素先出队列，这种数据结构就是优先级队列（PriorityQueue）。
不能插入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是创建小堆
JDK1.8中PriorityQueue底层采用了堆数据结构，堆其实就是对完全二叉树的元素作出了一些调整
所谓堆就是将一组数据按照完全二叉树的顺序存储方式存储，保证每一个根结点元素大于它的孩子结点的元素（大根堆）或者小于它的孩子结点的元素（小根堆），堆中某个结点的值总是不大于或着不小于其父节点的值。堆是一颗完全二叉树。
比较器
Comparable和Comparator都是两个接口，接口都可以用来实现集合中元素的比较、排序，Comparator位于包java.util下，而Comparable位于包java.lang下，Comparable接口将比较代码嵌入自身类中，而Comparator既可以嵌入到自身类中，也可以在一个独立的类中实现比较。
Integer、String等这些基本类型的JAVA封装类都已经实现了Comparable接口，这些类对象本身就支持自比较，直接调用Collections.sort()就可以对集合中元素的排序，无需自己去实现Comparable接口。而有些自定义类的List序列，当这个对象不支持自比较或者自比较函数不能满足你的要求时，你可以写一个比较器来完成两个对象之间大小的比较，也就是指定使用Comparator（临时规则排序，也称作专门规则排序），如果不指定Comparator，那么就用自然规则排序，这里的自然顺序就是实现Comparable接口设定的排序方式。
Top-k问题
求前k个最大，建小堆
求前k个最小，建大堆
代码示例
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按
任意顺序 返回答案。
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
public int[] topKFrequent(int[] nums, int k) {
Map<Integer,Integer> map=new HashMap<>();
for (int num : nums) {
int orDefault = (int) map.getOrDefault(num, 0);
map.put(num,orDefault+1);
}
// PriorityQueue<Map.Entry<Integer, Integer>> queue=new PriorityQueue<>(new Comparator<Map.Entry<Integer, Integer>>() {
// @Override
// public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
// return o1.getValue()-o2.getValue();
// }
// });
PriorityQueue<Map.Entry<Integer, Integer>> queue=new PriorityQueue<>((o1, o2) -> o1.getValue()-o2.getValue());
for (Map.Entry<Integer, Integer> integerIntegerEntry : map.entrySet()) {
queue.add(integerIntegerEntry);
if(queue.size()>k)
queue.poll();
}
System.out.println(queue);
int[] dp=new int[k];
for(int i=k-1;i>=0;i--){
dp[i]=queue.poll().getKey();
}
return dp;
}Comparable可以认为是一个内比较器，实现了Comparable接口的类有一个特点，就是这些类是可以和自己比较的，至于具体和另一个实现了Comparable接口的类如何比较，则依赖compareTo方法的实现
public class Person implements Comparable<Person>{
private String username;
private Integer age;
@Override
public int compareTo(Person o) {
return this.age-o.age;
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由半码博客整理，本文链接：https://www.bmabk.com/index.php/post/143056.html
