Java优先队列 priority queue

Java优先队列 priority queue 完整攻略

Java中的优先队列是一种特殊的队列，它允许在添加元素时指定一个优先级，并且在取出元素时总是取出当前队列中优先级最高的元素。内部实现采用堆来维护元素的优先级，时间复杂度为 O(log n)。

基本使用方法

Java提供了PriorityQueue类来实现优先队列，其默认是按照元素的自然顺序来排序的，也可以通过构造器提供一个Comparator来指定元素的排序规则。

// 创建一个默认的优先队列
PriorityQueue<Integer> pq = new PriorityQueue<>();
// 添加元素
pq.add(3);
pq.add(1);
pq.add(2);
// 取出元素，如果队列为空，则返回null
while (!pq.isEmpty()) {
    System.out.println(pq.poll());
}

上述代码输出结果为：

1
2
3

自定义排序规则

如果需要自定义元素的排序规则，可以通过实现Comparator接口来实现。

// 按照元素的长度来排序的比较器
Comparator<String> cmp = new Comparator<String>() {
    @Override
    public int compare(String s1, String s2) {
        return s1.length() - s2.length();
    }
};
PriorityQueue<String> pq = new PriorityQueue<>(cmp);
pq.add("java");
pq.add("python");
pq.add("c++");
pq.add("php");
while (!pq.isEmpty()) {
    System.out.println(pq.poll());
}

上述代码输出结果为：

php
java
c++
python

示例一：使用优先队列解决TOP K问题

TOP K问题是指从一个数列中查找出前K个最大或最小的数，可以使用最大或最小堆来解决。下面给出一个使用优先队列来解决TOP K问题的示例。

int[] nums = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
int k = 3;
PriorityQueue<Integer> pq = new PriorityQueue<>(k);
for (int num : nums) {
    if (pq.size() < k) {
        pq.add(num);
    } else if (num > pq.peek()) {
        pq.poll();
        pq.add(num);
    }
}
while (!pq.isEmpty()) {
    System.out.println(pq.poll());
}

上述代码输出结果为：

5
5
6

示例二：合并K个有序链表

给定K个有序链表，将它们合并成一个有序链表，可以使用优先队列来实现。

public ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o.val));
    for (ListNode node : lists) {
        if (node != null) {
            pq.add(node);
        }
    }
    ListNode dummy = new ListNode(-1);
    ListNode tail = dummy;
    while (!pq.isEmpty()) {
        ListNode node = pq.poll();
        tail.next = node;
        tail = tail.next;
        if (node.next != null) {
            pq.add(node.next);
        }
    }
    return dummy.next;
}

以上代码中的ListNode是链表节点的定义，比较函数采用了Java8中的新特性，这里使用Comparator.comparingInt(o -> o.val)来按照链表节点的值进行比较。