优先级队列

优先级队列是一种先进先出的数据结构，操作的数据带有优先级，这种数据结构就是优先级队列（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/197023.html