Java优先队列/堆（PriorityQueue）中三种重写compare的方法，TopK问题的解决思想及练习题（查找和最小的K对数字、最后一块石头重量）_priorityqueue compare

compare接口

因为在java的库当中优先队列是默认的建小堆，所以在使用的时候要进行修改根据情况来判断建大堆还是小堆。
所以要利用compare接口进行重写，其中有三种方法。

创建类

手动定义一个比较器对象改变建堆的方式，借助比较器对象，在优先队列中传入比较器。创建新的类，实现compare接口。

import java.util.Comparator;
import java.util.PriorityQueue;
public class Test {
    static class MyComp implements Comparator<Integer>{
        @Override
        public int compare(Integer o1, Integer o2) {
            //如果认为01优先级比o2高，先出o1 compare返回<0的整数
            //如果认为02优先级比o1高，先出o2 compare返回>0的整数
            //如果一样，返回0
            return o2 - o1;
        }
    }
    public static void main(String[] args) {
        PriorityQueue<Integer> queue = new PriorityQueue<>(new MyComp());
        queue.offer(9);
        queue.offer(5);
        queue.offer(2);
        queue.offer(0);
        queue.offer(3);
        queue.offer(4);
        queue.offer(7);

        while (!queue.isEmpty()){
            Integer cur = queue.poll();
            System.out.print(cur+" ");
        }
    }
}
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

匿名内部类

匿名内部类：不知类名的写到方法中的类，不知道类名，但是知道类实现了comparator接口

import java.util.Comparator;
import java.util.PriorityQueue;
public class Test {

    public static void main(String[] args) {
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });

        queue.offer(9);
        queue.offer(5);
        queue.offer(2);
        queue.offer(0);
        queue.offer(3);
        queue.offer(4);
        queue.offer(7);

        while (!queue.isEmpty()){
            Integer cur = queue.poll();
            System.out.print(cur+" ");
        }
    }
}
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

lambda表达式（java8中新加）

相当于一个匿名方法，无方法名。

import java.util.PriorityQueue;
public class Test {

    public static void main(String[] args) {
        PriorityQueue<Integer> queue = new PriorityQueue<>((o1,o2) -> o2 -o1);

        queue.offer(9);
        queue.offer(5);
        queue.offer(2);
        queue.offer(0);
        queue.offer(3);
        queue.offer(4);
        queue.offer(7);

        while (!queue.isEmpty()){
            Integer cur = queue.poll();
            System.out.print(cur+" ");
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

TopK问题

给定一个集合，找到前K个最大的或者最小的元素。

找前k最大为例：
1、针对整个集合，把N个元素建个堆，循环取 k次堆顶元素。如果把N个元素建堆，然后出队列N次就得到一个有序序列。
2、建立一个大小为k的小堆，堆顶元素就是k’个元素中的最小值，之后循环遍历集合当中的每个元素，分别和堆顶元素进行比较，如果大于就把堆顶元素替换成当前元素，之后进行向下调整，得到新的堆顶，当把所有的元素遍历完毕，所建的小堆中的元素就是前k大的值。
N>>k，第一个方案的时间空间效率低于第二个，N太大无法同时加载到内存中。 第二种得到的前k个元素是无序的，如何要按顺序，还需要重新排序。N和k大小差不多时两者都可以。

查找和最小的k对数字

思路：

1、定义一个类，表示数据，然后创建二维顺序表，先判断k的合法性。
2、之后建一个数据类型的优先队列，并设置比较器，根据数据的和sum从到大排列。
3、把所有的数据都放入优先队列中，循环取出队列中的最大值，每取出一个建一个顺序表tmp用来存储，之后再加到总的表result中。
4、循环直到队列为空。最后返回总表result。

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
public class Solution {
    //定义一个类描述数对
    static class Pair{
        public int num1;
        public int num2;
        public int sum;
        public Pair(int num1,int num2){
            this.num1 = num1;
            this.num2 = num2;
            this.sum = num1 + num2;
        }
    }
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<List<Integer>> result = new ArrayList<>();
        if( k<= 0){
            return result;
        }
        //准备一个堆，指定一个比较器对象
        PriorityQueue<Pair> queue = new PriorityQueue<>(new Comparator<Pair>(){//优先队列的类型为Pair
            public int compare(Pair o1,Pair o2){
                return o1.sum - o2.sum;
            }
        });
        //构造出所有的数对，存放到queue之中
        for(int i = 0; i<nums1.length; i++){
            for(int j = 0; j<nums2.length; j++ ){
                queue.offer(new Pair(nums1[i],nums2[j]));
            }
        }
        for(int i = 0;i < k && !queue.isEmpty(); i++){
            Pair cur = queue.poll();
            List<Integer> tmp = new ArrayList<>();
            tmp.add(cur.num1);
            tmp.add(cur.num2);
            result.add(tmp);
        }
        return result;
    }
}
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
40
41
42
43
44

最后一块石头重量

思路：

1、把数组中所有的数据放到优先队列中，之后每次取最大的两个。
2、如果两个相等则不操作直到最后只剩了两个元素而且相等则返回0，如果两个不相等，大的值减去小的值，差值重新放入优先队列中，直到队列的长度等于1。

public class Solution {
    public static int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        if(stones.length == 0){
            return 0;
        }
        for(int i = 0;i<stones.length;i++){
            queue.offer(stones[i]);
        }
        while (queue.size()>1){
            int y = queue.poll();
            int x = queue.poll();
            int z = 0;
            if(x == y && queue.size() == 0){
                return 0;
            }
            if(x != y){
                 z = y - x;
                queue.offer(z);
            }
        }
        int k = queue.poll();
        return k;
    }
}
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