Binary Heap Priority Queue
This is the most common implementation but not the only one.
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.
Quickly access the highest-priority item. Priority queues allow you to peek at the top item in while keeping other operations relatively cheap ().
Slow enqueues and dequeues. Both operations take time with priority queues. With normal first-in, first-out queues, these operations are time.
- 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)
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)
A Sorted Array
- 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)
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.