博客

本人学习Java不久，在刷题过程中，对优先队列中大根堆，小根堆的使用有些不熟练，在这里做一个简单的学习记录。

单元素优先队列

首先，我们知道优先队列默认是小根堆，也就是堆顶是最小的元素，我们做个简单的试验：

PriorityQueue<Integer> heap = new PriorityQueue<>(
                (n1,n2) -> n1-n2  //这一句加不加结果是一样的
        );
        heap.add(4);
        heap.add(1);
        heap.add(2);
        heap.add(3);
        while(!heap.isEmpty())
        {
            System.out.println(heap.poll());
        }

输出顺序是1，2，3，4。

可以看到默认的比较规则就是n1-n2,如果我们改成n2-n1

        PriorityQueue<Integer> heap = new PriorityQueue<>(
                (n1,n2) -> n2-n1 //这一句加不加结果是一样的
        );

输出顺序就是4，3，2，1。

可以想见优先队列内部是按照比较器返回的结果进行处理的，一般认为a,b比较结果大于0，就是a大于b，等于0就是a等于b；小于0就是a小于b。

现在我们知道当比较n1,n2的时候，如果结果大于0(也就是默认的n1-n2>0)，那么要把n1下沉(默认的小根堆),当我们改成n2-n1的时候，结果大于0，证明n2大于n1,但还是n1（值较小的元素）下沉，于是这个堆就成了大根堆！

到这里我们可以假设，

PriorityQueue会在比较结果大于0的时候把第一个数下沉

，那么是大的数下沉还是小的数下沉，就可以由我们自己掌握了。

双元素优先队列

我们来验证一下，现在将优先队列中存储的一个元素改成有两个数的数组。

PriorityQueue<int[]> heap = new PriorityQueue<>(
                (pair1,pair2) -> pair1[0]-pair2[0]
        );
        heap.add(new int[]{1,9});
        heap.add(new int[]{2,8});
        heap.add(new int[]{3,7});
        while(!heap.isEmpty())
        {
            int[] cur = heap.poll();
            System.out.println(cur[0] + "," + cur[1]);
        }

这里我们必须是要设置比较规则的，因为默认里面没有比较数组的规则。这里我们设置第一个元组的第一个数减去第二个元组的第一个数。

按照前面设想的逻辑，此时如果结果大于0，证明pair2的第一个数比pair1的第一个数大，而pair1下沉，说明此时是

一个以元组的第一个数为比较依据的大根堆

。

查看输出结果：



猜想成立！

现在我们可以自由地依照我们的想法来设置排序规则了，比如我现在想要

以元组的和为比较依据，并且是小根堆

。

根据猜想，我们需要让大的值下沉，也就是比较结果大于0的时候，应该是第一个元组是大值

可以写得代码如下：

        PriorityQueue<int[]> heap = new PriorityQueue<>(
                (pair1,pair2) -> pair1[0]+pair1[1]-pair2[0]-pair2[1]
        );
        heap.add(new int[]{1,9});
        heap.add(new int[]{2,6});
        heap.add(new int[]{3,4});
        while(!heap.isEmpty())
        {
            int[] cur = heap.poll();
            System.out.println(cur[0] + "," + cur[1]);
        }

查看输出结果：



结果正确！

Arrays.sort()

在Arrays.sort中也可以自定义排序规则，试验后发现是一样的譬如：

int[][] arr = {{1,9},{2,8},{3,7}};
Arrays.sort(arr,(a,b)->b[0]-a[0]);

当结果大于0的时候，是a向后

，也就是默认的是升序，这里的代码的含义是以元组的第一个值为依据，降序排列。

需要注意的是如果是一维数组，是无法自定义这样的规则的，如果想换成降序，最简单的办法就是翻转：

 Arrays.sort(arr,Collections.reverseOrder());

注意这里的数组不能是int[],需要是Integer[]

探究结果

当我们想自定义优先队列的比较规则时，先想是大根堆还是小根堆，然后就知道结果大于0的时候应该是谁大，就可以写比较规则了！