Priority Queue

Intro

Priority queue is an abstract data type, in which each element has a "priority" associate with it. PQ supports operations such as findMin() in O(1), insert(element) and deleteMin in O(logn).

Here is a funny example from ADM: Single people maintain a priority queue of potential dating candidates—mentally if not explicitly. One’s impression on meeting a new person maps directly to an attractiveness or desirability score. Desirability serves as the key field for inserting this new entry into the “little black book” priority queue data structure. Dating is the process of extracting the most desirable person from the data structure (Find- Maximum), spending an evening to evaluate them better, and then reinserting them into the priority queue with a possibly revised score.

Heap

We can implement priority queue in different ways (unordered array, ordered array, linked list). One most efficient way is using a data structure called heap. A heap is a complete binary tree - all levels are full except the last level where all elements are placed to the left (So the height of the tree is guaranteed to be logn which will help out the runtime of our desired operations). In a min heap, all the children are greater than their parents. In a max heap, all parents are greater than their children.

Heap Implementation

Since the binary tree is complete, we know the location of the tree node if we know the index.

siftUp
siftDown
operations

Comparator

Define how to compare two objects

private Comparator<ListNode> HeapComp = new Comparator<ListNode>() {
    public int compare(ListNode n1, ListNode n2) {
        if (n1 == null) return 1;
        if (n2 == null) return -1;
        return n1.value - n2.value;
    }
};

In Java 8, interfaces with a single method can be written with lambda.

Comparator<ListNode> heapComp = (ListNode n1, ListNode n2) -> {n1.val - n2.val};

Min heap can use the default comparator or a natural ordering. Max heap takes a reversed comparator for the opposite ordering.

Queue<ListNode> minHeap = new PriorityQueue<>(k, heapComp);
Queue<ListNode> maxHeap = new PriorityQueue<>(k, Collections.reverseOrder(heapComp));

Questions

• Data Stream

• Closest K (max heap - polling the max)

• Top K (min heap - polling the min)

• Priority Search

References

• UW-Madison CS367 Lecture 24 Heaps and Priority Queues
• The Algorithm Design Manual Ch3.5 Priority Queue

• Heap and Heapsort by stoimen
• Algorithms, Part I - Week 4 Priority Queues by Robert Sedgewick
• Stack Overflow - Comparable vs Comparator
• Java Lambda Expressions by Jakob Jenkov