PriorityQueue的使用、leetcode前k个高频元素最大堆方法中“（(a, b) -＞ b[1] - a[1]）”的解释（java）_priorityqueue的比较器 lambda表达式

---

前言

 PriorityQueue<int[]> priorityQueue = new PriorityQueue<>((a, b) -> b[1] - a[1]);
1

(a, b) -> b[1] - a[1] 是lambda表达式，等价于以下写法

 PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
            public int compare(int[] m, int[] n) {
                return m[1] - n[1];
            }
1
2
3
4

继承Comparator<int[]>接口，并且实现其中的compare()方法。

---

提示：以下是本篇文章正文内容，下面案例可供参考

一、PriorityQueue类

public class PriorityQueue <.E>：基于优先级堆的无界优先级queue 。 优先级队列的元素根据其natural ordering或队列构造时提供的Comparator进行排序 ，具体取决于使用的构造函数。
优先级队列结构底层是二叉堆

PriorityQueue的构造方法：
本题用的构造方法：
PriorityQueue​(Comparator<? super E> comparator)
创建具有默认初始容量的 PriorityQueue ，其元素根据指定的比较器进行排序。

二、Comparator接口

Interface Comparator<.T>
参数类型
T - 此比较器可以比较的对象类型
Functional Interface:
这是一个功能接口，因此可以用作lambda表达式或方法引用的赋值目标。

方法摘要

三、什么是接口

接口的概念

接口不是类，而是对希望符合这个接口的类的一组需求。例如Arrays类中sort方法可以对对象数组进行排序，但对象所属类必须实现Comparable接口

Comparable接口代码(自然排序)：

public interface Comparable
{
int compareTo(Object other);
}
1
2
3
4

·任何实现Comparable接口的类都需要包含compareTo方法
·接口中所有方法都自动是public方法
·接口没有实例

假设用Arrays类的sort方法对Employee对象数组进行排序，Employee类必须实现Comparable接口：
1.将类声明为实现给定接口（用implements关键字）
class Employee implements Comparable
2.对接口中所有方法提供定义

要让一个类使用排序服务·必须让它实现compareTo方法
如：

因为要向sort方法提供对象的比较方法

为什么不能在Employee类中直接提供compareTo的方法？
因为在调用方法时编译器要检查这个方法是不是确实存在，例如在sort方法中出现if(a[i].compareTo(a[j])>0)
编译器必须确认a[i]有一个compareTo方法，如果a是一个Comparable对象的数组就可以确保拥有该方法

四、lambda表达式

假设要计算first.length()-second.length()
lambda表达式为：
(String first,String second)->first.length()-second.length()
lambda表达式是一个代码块以及必须传入的变量范围

如果可以推导出lambda表达式的参数类型则可以忽略其类型
如前言中的代码

五、Comparator比较器用法

Collections.sort(list, new Comparator<Node>() {
    /**o1-o2为升序序排列，o2-o1为降序排列，若具体到某一字段，则根据该字段进行排列*/
    @Override
    public int compare(Node o1, Node o2) {
        if (o1.x==o2.x) //若x属性相等，根据y来升序
            return o1.y-o2.y;
        return o1.x-o2.x;//x属性不相等，根据x来升序排列
    }
});
1
2
3
4
5
6
7
8
9

---

参考

·《Java技术核心卷1》
·CSDN博主苍白的咏叹调 《Java 的Comparator比较器用法》
链接：https://blog.csdn.net/kuishao1314aa/article/details/100527985

-------- 2023/4/27--------
原题的评论区的（用最大堆）解法：

class Solution {
     public int[] topKFrequent(int[] nums, int k) {
        //先统计每个数字出现的次数
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums)
            map.put(num, map.getOrDefault(num, 0) + 1);

        //最大堆
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>((a, b) -> b[1] - a[1]);
        for (int key : map.keySet())
            priorityQueue.add(new int[]{key, map.get(key)});

        //取堆中最大的k个元素
        int[] res = new int[k];
        for (int i = 0; i < k; i++)
            res[i] = priorityQueue.poll()[0];
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

重点在：

priorityQueue.add(new int[]{key, map.get(key)});
1

结合

lambda表达式是一个代码块以及必须传入的变量范围

可以知道a[]和b[]范围是2，也就是a[0] b[0]（代表key）a[1] b[1]（代表value）

//按value值升序排序
 PriorityQueue<int[]> priorityQueue = new PriorityQueue<>((a, b) -> b[1] - a[1]);
//按key值升序排序
 PriorityQueue<int[]> priorityQueue = new PriorityQueue<>((a, b) -> b[0] - a[0]);
 //超出范围，会报错（假如我写2的话）
 //b[2] - a[2]
 
1
2
3
4
5
6
7