集合之PriorityQueue的使用_new priorityqueue<>(new comparator()

PriorityQueue实现了Queue接口，所以属于队列
PriorityQueue最大的特点是，时刻保持有序(最重要的特性)
构造参数中加入Comparator，可以自定义排序方式

	PriorityQueue<ListNode> listNodes = new PriorityQueue<>(new Comparator<ListNode>() {
        @Override
        public int compare(ListNode o1, ListNode o2) {
            return o1.val - o2.val;
        }
    });
1
2
3
4
5
6

poll();返回第一个对象并移除
peek();只返回不移除

例题：
leetcode第23题
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6

如果使用PriorityQueue，比较容易理解

public ListNode mergeKLists(ListNode[] lists) {
    //创建PriorityQueue，比较值为val
    PriorityQueue<ListNode> listNodes = new PriorityQueue<>(new Comparator<ListNode>() {
        @Override
        public int compare(ListNode o1, ListNode o2) {
            return o1.val - o2.val;
        }
    });
    //将数组中的值，转移到PriorityQueue中
    for (int i = 0; i < lists.length; i++) {
        if (lists[i] == null) {
            continue;
        }
        listNodes.add(lists[i]);
    }
    if (listNodes.isEmpty()) {
        return null;
    }
    //拿到首位
    ListNode ans = listNodes.poll();
    ListNode node = ans;
    if (node.next != null) {
        listNodes.add(node.next);
    }
    while (!listNodes.isEmpty()) {
        //规则，拿到值首位值最小链表，将第一位添加到需要返回的链表,如果该链表尚未结束，再添加回PriorityQueue中
        ListNode nNode = listNodes.poll();
        node.next = nNode;
        node = nNode;
        if (node.next != null) {
            listNodes.add(node.next);
        }
    }
    return ans;
}
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