8/1/2017 - 6:03 PM

priority queue operation

priority queue operation

// create a priority queue
// To create a prioirty queue, user need to pass a compartor to it. And also indicate
// the size of the queue
Queue<ListNode> heap = new PriorityQueue<ListNode>(lists.size(), ListNodeComparator);

// comparator
// Returns a negative integer, zero, or a positive integer as the first argument is
// less than, equal to, or greater than the second.
private Comparator<ListNode> ListNodeComparator = new Comparator<ListNode>() {
    public int compare(ListNode left, ListNode right) {
        return left.val - right.val;
默认情况下,priority queue是升序排列的,所以第一个元素是最小的。

java8 comparator:
Queue<Pair> heap = new PriorityQueue<Pair>(row*col, (Pair p1, Pair p2) -> (p1.val - p2.val));

// add element

// remove all elements

// insert 

// pop top element

// peek

// remove

// check size

// note
// heap.add() and heap.offer() are identical in priority queue
// however, in a queue
// heap.add() always return true but throw exception if queue is full
// can return false if queue if full

// time complexity
Implementation note: this implementation provides O(log(n)) time for the enqueing and dequeing methods (offer, poll, remove() and  add); 
linear time for the remove(Object) and contains(Object) methods; 
and constant time for the retrieval methods (peek,  element, and size).