Java PriorityQueue

PriorityQueue的介绍以及应用。

基本理论

我们知道队列是遵循先进先出(First-In-First-Out)模式的,但有些时候需要在队列中基于优先级处理对象。
PriorityQueue就是一种基于优先级堆的极大优先级队列。优先级队列是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素。如果不提供Comparator的话,优先队列中元素默认按自然顺序排列,也就是数字默认是小的在队列头,字符串则按字典序排列(参阅 Comparable),也可以根据 Comparator 来指定,这取决于使用哪种构造方法。

具体来说,PriorityQueue具备以下特性:

  • 不允许使用 null 元素, 而且不支持non-comparable(不可比较)的对象
  • 优先队列的大小是不受限制的,但在创建时可以指定初始大小。当我们向优先队列增加元素的时候,队列大小会自动增加。
  • 不是线程安全的, 如有此方面需求可以考虑使用线程安全的PriorityBlockingQueue。
  • 此实现为插入方法(offer、poll、remove() 和 add 方法)提供 O(log(n)) 时间;
    为 remove(Object) 和 contains(Object) 方法提供线性时间;
    为检索方法(peek、element 和 size)提供固定时间。
  • 可以在构造函数中指定如何排序。PriorityQueue(int initialCapacity, Comparator comparator)
    使用指定的初始容量创建一个 PriorityQueue,并根据指定的比较器comparator来排序其元素。比如我们有一个自定义类MyClass,它没有提供任何类型的排序。当我们用它建立优先队列时,应该为其提供一个比较器对象。

一个栗子

看个例子吧,对上面所说的也就了然于胸了。

题目是:假设有k个已经排好序的list,现在需要将其合并成一个排序的list。

public ListNode mergeKLists(ListNode[] lists) {
    if (lists.length == 0)
        return null;

    //PriorityQueue is a sorted queue
    PriorityQueue<ListNode> q = new PriorityQueue<ListNode>(lists.length,
            new Comparator<ListNode>() {
                public int compare(ListNode a, ListNode b) {
                    if (a.val > b.val)
                        return 1;
                    else if(a.val == b.val)
                        return 0;
                    else
                        return -1;
                }
            });

    //add first node of each list to the queue
    for (ListNode list : lists) {
        if (list != null)
            q.add(list);
    }

    ListNode head = new ListNode(0);
    ListNode p = head; // serve as a pointer/cursor

    while (q.size() > 0) {
        ListNode temp = q.poll();
        //poll() retrieves and removes the head of the queue - q.
        p.next = temp;

        //keep adding next element of each list
        if (temp.next != null)
            q.add(temp.next);

        p = p.next;
    }

    return head.next;

}