PriorityQueue与Comparator

发表于 更新于 分类于 ， 阅读次数：

PriorityQueue的使用场景

1
2
3
4
5
Queue<Integer> queue1 = new PriorityQueue<>();

Queue<Integer> queue2 = new PriorityQueue<>(Comparator.comparingInt(o -> o));

Queue<Integer> queue3 = new PriorityQueue<>(Comparator.comparingInt(o -> -o));

Java中的PriorityQueue常用于实现小顶堆、大顶堆。由上述代码可见，通常有默认无参构造函数、传入Comparator对象等方式的实现。

困惑

从构造函数层面，完全不清楚默认构造函数的排序规则，也完全不明白Comparator实现的comparingInt方法对应的排序规则。

根据网上绝大多数文章的描述，都没有解释或者只是说明了对应的排序规则，但是不知道为什么是对应升序或降序。通过阅读源码，才得到准确的认知。

阅读源码

PriorityQueue构造函数、增删元素

image-20240417200527177

可以看到，无参构造函数和指定了Comparator的构造函数实际都是指向PriorityQueue(int initialCapacity, Comparator<? super E> comparator)构造函数。而comparator发挥作用的时候，体现在PriorityQueue增删元素的方法中，以offer方法为例：

image-20240417202910975

根据构造函数是否传入了Comparator对象，元素的比较分别执行siftUpUsingComparator和siftUpComparable方法，两个方法的逻辑一致，只是Comparator通常作为外部排序工具，Comparable作为对象的内部比较方式。

  • 修改范围：Comparable 通常作为对象的内部比较方式，适合单一的自然排序；而 Comparator 作为外部工具，可以定义多种排序方式。
  • 灵活性：Comparator 更加灵活，允许不同的排序策略，且可以在不修改原有类的情况下实现。
  • 应用场景：如果排序方式只有一种，或者是对象的自然顺序，推荐使用 Comparable；如果需要多种排序方式，或者不希望修改原有类的结构，推荐使用 Comparator。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private static <T> void siftUpUsingComparator(
        int k, T x, Object[] es, Comparator<? super T> cmp) {
    while (k > 0) {
        // 无符号右移，找到父节点索引下标
        int parent = (k - 1) >>> 1;
        Object e = es[parent];
        // 将当前元素和父节点进行比较，结果>=0 跳出循环
        if (cmp.compare(x, (T) e) >= 0)
            break;
        // < 0，则交换当前元素和父节点的位置
        es[k] = e;
        k = parent;
    }
	// 将当前元素x放入到最终确定的位置
    es[k] = x;
}

可知，cmp.compare()方法的返回值< 0时，当前元素与父节点交换位置。siftUpComparable方法也是相同，是在不传入Comparator对象也能进行大小比较的前提下，通过Comparable的compareTo()方法进行比较。

1
2
3
4
5
6
7
8
9
10
11
12
private static <T> void siftUpComparable(int k, T x, Object[] es) {
        Comparable<? super T> key = (Comparable<? super T>) x;
    while (k > 0) {
        int parent = (k - 1) >>> 1;
        Object e = es[parent];
        if (key.compareTo((T) e) >= 0)
            break;
        es[k] = e;
        k = parent;
    }
    es[k] = key;
}

Comparator.comparingInt()

1
2
3
4
5
public static <T> Comparator<T> comparingInt(ToIntFunction<? super T> keyExtractor) {
    Objects.requireNonNull(keyExtractor);
    return (Comparator<T> & Serializable)
        (c1, c2) -> Integer.compare(keyExtractor.applyAsInt(c1), keyExtractor.applyAsInt(c2));
}

由Comparator.comparingInt()的代码可知，它接收一个ToIntFunction作为参数。
o -> o是一个lambda表达式，将元素本身作为整数值返回，实现了小顶堆的效果。

1
new PriorityQueue<>(Comparator.comparingInt(o -> o));

总结

PriorityQueue的排序规则，依赖于cmp.compare()的具体实现。cmp.compare()方法的返回值< 0时，当前元素与父节点交换位置。

以数值大小进行直接比较的自然排序为例，数值较小的元素总是会成为父节点，最终形成小顶堆的效果。