Interview Cake
Quick reference
Binary Heap Priority Queue
This is the most common implementation but not the only one.
| Worst Case | |
|---|---|
| space | |
| peek | |
| dequeue | |
| enqueue |
A priority queue is a special queue where:
- Every item in the queue has a priority, and
- Higher-priority items are dequeued before lower-priority items.
Picture a big list of bugs for an engineering team to tackle. You want to keep the highest-priority bugs at the top of the list.
Strengths:
-
Quickly access the highest-priority item. Priority queues allow you to peek at the top item in while keeping other operations relatively cheap ().
Weaknesses:
-
Slow enqueues and dequeues. Both operations take time with priority queues. With normal first-in, first-out queues, these operations are time.
Uses
- Any time you want to handle things with different priority levels: triaging patients in a hospital, locating the closest available taxi, or just a to-do list.
- Operating system schedulers may use priority queues to select the next process to run, ensuring high-priority tasks run before low-priority ones.
-
Certain foundational algorithms rely on priority queues:
- Dijkstra's shortest-path
- A* search (a graph traversal algorithm like BFS)
- Huffman codes (an encoding for data compression)
Implementation
Binary Heaps
Priority queues are often implemented using binary heaps. Notice how the highest priority is right at the top of the heap, ready to be grabbed in time.
- To enqueue an item, add it to the heap using the priority as the key. ( time)
- To peek at the highest priority item, look at the item at the top. ( time)
- To dequeue the highest priority item, remove the top item from the heap. ( time)
Other Options
A Sorted List
- To enqueue, use binary search to figure out where the new item should go. Then scoot items over to make space for the new item. ( time, since in the worst case you have to scoot everything over to make room)
- To peek at the highest priority item, look at the item at index zero. ( time)
- To dequeue, scoot every item forward one index. ( time)
A Sorted Linked List
- To enqueue, walk through the linked list to figure out where the new item should go. Then, reassign pointers to add the new item. ( time)
- To peek at the highest priority item, look at the item at the head of the linked list. ( time)
- To dequeue, update the linked list's head pointer to point to the second item. (And deallocate the old head node, if you're using a language with manual memory management.) ( time)
Fancier Heaps
Binary heaps are just one kind of heap. Other kinds of heaps (e.g.: Fibonacci heaps or binomial heaps) can offer faster average performance for some priority queue operations. But, they're much more complex than binary heaps and less commonly used in practice.
In a coding interview, you usually can't go wrong by using a binary-heap based priority queue.
See also:
Interview coming up?
Get the free 7-day email crash course. You'll learn how to think algorithmically, so you can break down tricky coding interview questions.
No prior computer science training necessary—we'll get you up to speed quickly, skipping all the overly academic stuff.
No spam. One-click unsubscribe whenever.
You're in! Head over to your email inbox right now to read day one!
