Priority Queues

Queues

• So far, we've only looked at strict FIFO (objects returned in order or insertion)
• Doesn't model real world too well
• Airport check-in (first class, gold card members, frequent flyers)
• Emergency room at hospital

Priority Queues

• Give preference to higher priority
• Value with current highest priority is always removed first
• Same methods as Queue: offer, poll, peek, size

Try It Out

• Assume you have an already functioning max-heap called maxHeap
• maxHeap contains the following methods (insert, removeMax, size)
• Create a PriorityQueue class which used a max heap

Linked List

• Insert items into correct place in list (O(n))
• Remove items from front of list (O(1))
• Insertion of high priority items is fast (inserted closer to front, better real time performance, doesn't change big-o however)

Arrays

• Objects inserted at proper location in array
• All other objects must be shifted to make room (O(n))
• Objects can be removed from the front and the entire array shifted down (O(n))
• A circular array can be used for polling (O(1))

Binary Search Tree

• Items are inserted into tree using priority as key (O(n))
• Items are removed from leftmost or rightmost node of tree (O(n))
• Balanced trees would provide better performance

Heap

• Objects are inserted into heap using priority as key (O(log n))
• Items are removed from heap in O(log n) time
• Peeking is constant time
• Simplest algorithm with guaranteed log time operations

Java's Priority Queue

• http://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html