Introduction
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.
Advantages
- Quickly access the highest-priority item. Priority queues allow you to peek at the top item in O(1) while keeping other operations relatively cheap O(log(n)).
Disadvantages
- Slow enqueues and dequeues. Both operations take O(log(n)) time with priority queues. With normal first-in, first-out FIFO queues, these operations are O(1) time.
Time Complexity
n is the number of nodes in the Priority Queue
| Operation |
Big-O |
| Peek |
O(1) |
| Dequeue |
O(log(n)) |
| Enqueue |
O(log(n)) |
Space Complexity
n is the number of nodes in the Priority Queue
**O(n**)
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 O(1) time.