The Priority Queue

A priority queue is a collection where every removal returns the element with the highest priority. In this chapter, you will see why every flat design leaves at least one operation at $O(n)$, and you will work by hand with the binary heap, the design that brings every operation down to $O(\log n)$ or better. In the next chapter, you will implement the binary heap.

After reading this chapter, you should be able to:

• Specify the Priority Queue ADT and its contract in Javadoc
• Explain why every flat design for a priority queue, whether unsorted or sorted, leaves at least one operation at $O(n)$
• Decide whether a binary tree is a binary heap by checking the structure property and the order property
• Trace peek, add (swim up), and remove (sink down) on a binary heap, one operation at a time and as a sequence
• Explain why swimming up after add and sinking down after remove restore the order property
• Show that peek is $O(1)$ and that add and remove are $O(\log n)$, because a complete binary tree of $n$ nodes has height about $\log n$

Sections

1. The Emergency Room
2. The Priority Queue ADT
3. Priority Queue ADT Specification
4. Should a Priority Queue Be Iterable?
5. Two Unsorted Designs
6. A Sorted Design
7. The Binary Heap
8. The Structure Property
9. The Order Property
10. add: Insert and Swim Up
11. remove: Replace the Root and Sink Down
12. Tracing a Heap
13. Tracing peek, remove, and add
14. The Height of a Heap
15. Why Every Operation Is O(log n) or Better