堆和优先队列_小顶堆和优先队列

首先要了解什么是堆，大顶堆，小顶堆，优先队列的概念。
https://www.cnblogs.com/lanhaicode/p/10546257.html
Java中的优先队列默认是小顶堆形式

PriorityQueue<Integer> pq = new PriorityQueue<>();
1

若要改成大顶堆，则需要lambada表达式

PriorityQueue<Integer> pq = new PriorityQueue<>((a,b) -> {return b -a;});
1

优先队列常常用来解决 top k 的问题

215. 数组中的第K个最大元素（优先队列）

注意：本题还可以使用快速排序的分区思想，这里先不做介绍，等排序章节再总结。

class Solution {
    public int findKthLargest(int[] nums, int k) {
        /**
        分析：
        典型的求解top k 问题，应该想到优先队列（堆这种数据结构）
         */
         // 排序法解题，面试等通知吧
        // Arrays.sort(nums);
        // return nums[nums.length - k];

        // 使用优先队列（默认是小顶堆，这里使用lambda表达式改成大顶堆）
        PriorityQueue<Integer> pq = new PriorityQueue<>((a,b) -> {return b -a;});
        // 储存到堆内
        for(int i = 0; i < nums.length; i++){
            pq.add(nums[i]);
        }
        // 取出前k - 1个
        for(int i = 0; i < k - 1; i++){
            pq.remove();
        }
        // 第k大元素
        return pq.peek();

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

347. 前 K 个高频元素(哈希表+优先队列)

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 计算频率 使用哈希表
        // 取前k个  使用优先队列（内部使用堆结构）
        Map<Integer,Integer> map = new HashMap<>();
        for(int num:nums){
            map.put(num,map.getOrDefault(num,0) + 1);
        }
        // 定义优先队列
        Queue<Integer> pq = new PriorityQueue<>((o1,o2) -> map.get(o2) - map.get(o1));
        // 储存所有的键
        pq.addAll(map.keySet());
        int[] res = new int[k];
        // 取前k个
        for(int i = 0; i < k; i++){
            res[i] = pq.remove();
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

703. 数据流中的第 K 大元素（小顶堆+维护k个容量=堆顶是第k大值）

class KthLargest {
    /**
    分析：
    这是一个设计题，但是还是求 top k的问题
     */
    private int k;
    // private int[] nums;
    private PriorityQueue<Integer> pq ;
    public KthLargest(int k, int[] nums) {
        // 初始化
        this.k = k;
        // 小顶堆的大小限制为k个，堆顶值刚好就是第k大的元素
        pq = new PriorityQueue<>(k);
        // 添加元素
        for(int num:nums){
            add(num);
        }
    }
    
    public int add(int val) {
        // 优先队列内容量不足 k个 直接添加val
        // 这个小顶堆 就是一直在维护容量为k的堆，堆顶值就是第k大元素
        if(pq.size() < k){
            pq.add(val);
        }else if(val > pq.peek()){
            // 新加元素和堆顶比较 比堆顶元素小则丢弃，否则删除堆顶元素，插入新元素
            pq.remove();
            pq.add(val);
        }
        return pq.peek();

    }
}

/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest obj = new KthLargest(k, nums);
 * int param_1 = obj.add(val);
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

973. 最接近原点的 K 个点（大顶堆+维护k个容量=超过k则移除堆顶，余下就是k个最小值）

class Solution {
    // 本题是求前 K 小，因此用一个容量为 K 的大根堆，每次 remove 出最大的数，那堆中保留的就是前 K 小啦！
    // 大顶堆
    public int[][] kClosest(int[][] points, int K) {
        PriorityQueue<int[]> pq
        //  关于二维数组如何重写lambda表达式？
                = new PriorityQueue<>(K , (a, b) -> (b[0] * b[0] + b[1] * b[1]) - (a[0] * a[0] + a[1] * a[1]));

        for (int[] point : points) {
            // 添加到大根堆中
            pq.add(point);
            // 堆内容量超过k个，那么移除堆顶，余下的k个元素就是 k个最小值
            if (pq.size() > K) pq.remove();
        }

        // 堆中存储的就是出现了前 k 个高频的元素（最小值）
        int[][] res = new int[K][2];
        int index = 0;
        while (!pq.isEmpty()) {
            res[index++] = pq.remove();
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

总结703和973，典型的top k 问题，但是用到了一些数学的技巧，维护堆内的元素个数。输出想要的结果。常见操作如703，小顶堆+维护k个=堆顶就是第k大元素。又如973，大顶堆+维护k个=超过k个就移除堆顶，余下的k个就是最小值组成的

其中还学习了lambda表达式。

普通数：实际上是 (int a,int b)
((a,b) -> {return a - b;});  这是升序排序
((a,b) -> {return b - a;});  这是降序排序
一维数组：实际上是 (int []a,int []b)
((a, b) ->  a[0] * a[0] + a[1] * a[1]) - (b[0] * b[0] + b[1] * b[1]));  按照离原点距离升序排序
((a, b) ->  b[0] * b[0] + b[1] * b[1]) - (a[0] * a[0] + a[1] * a[1]));  按照离原点距离降序排序
二维数组：实际上是 (int [][]a,int [][]b)
((a,b) -> a[0] - b[0]); 按照二维数组中一维数组第一个数升序排序
((a,b) -> b[0] - a[0]); 按照二维数组中一维数组第一个数降序排序

((a,b) -> a[1] - b[1]); 按照二维数组中一维数组第二个数升序排序
((a,b) -> b[1] - a[1]); 按照二维数组中一维数组第二个数降序排序

1
2
3
4
5
6
7
8
9
10
11
12
13

观察以上柿子可以知道，若定义变量 (a,b),这里不管是一维还是二维，只要后续是a在前就是 升序，反之降序。
对于二维数组也很好理解 (int [][] a,int [][] b) 那么a[0] 就是一维数组

1046. 最后一块石头的重量（大顶堆）

class Solution {
    public int lastStoneWeight(int[] stones) {
        /**
        分析：
        有点像开心消消乐，本质上还是top k的问题
         */
         PriorityQueue<Integer> pq = new PriorityQueue<>((a,b) -> b - a);
         for(int weight:stones){
             pq.add(weight);
         }
         while(pq.size() > 1){
             int y = pq.remove();
             int x = pq.remove();
             if( x != y){
                 pq.add( y - x);
             }
         }
         // 大顶堆非空 才输出
         if(!pq.isEmpty())
            return pq.peek();
        // 都被粉碎了 就返回 0
        return 0;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25