CS Level Up Series (28 Part Series)
- Priority Queues are often implemented using binary heaps.
- Accessing the highest priority item (front of the queue) is fast. O(1) (constant).
- However, enqueuing/dequeueing (adding/removing) items is slower than regular queues at O(log(n)) (logarithmic). This is due to items having a priority - so each time an item is introduced/removed behind the scenes a reshuffling/ordering of the items might take place.
- Priority queues often get used in graph algorithms (like Dijkstra's algorithm or Prim's algorithm). They can be useful for scheduling things as well - such as jobs/tasks. There is also an interesting Microsoft Azure article explaining the use cases/patterns for priority queues.
- Space is O(n).
As I had just learned binary heaps, priority queues were straightforward. All I needed to do to implement one was alter my previous min-heap and add a thin class for the queuing operations.
Here's the finished implementation, with test code, of a priority queue with a min-heap (smaller means higher priority). For readability, I moved the min-heap code below the priority queue and
As always, if you found any errors in this post please let me know!
Claim your page on DEV before someone else does
Level up every day