CS Level Up Series (30 Part Series)
1) CS Level Up Series Introduction
2) Dynamic Arrays
3 ... 28
3) Linked Lists
4) Stacks
5) Queues
6) Hash Tables
7) Binary Search Trees
8) Binary Heaps
9) Priority Queues
10) Graphs
11) Tries
12) Binary & Bit Manipulation
13) Common Sorting Algorithms
14) Searching Algorithms
15) Permutations, Combinations, & Subsets
16) NP-Complete & Fibonacci Heap
17) Detecting Graph Cycles With Depth-First Search
18) Finding Shortest Paths In Graphs (using Dijkstra's & BFS)
19) Topological Sorting of Directed Acyclic Graphs (DAGs)
20) Finding Articulation Points & Bridges in Undirected Graphs
21) Finding Strongly Connected Components in Directed Graphs using Tarjan's Algorithm
22) Checking If An Undirected Graph Is Bipartite
23) Extending An Iterator
24) Union-find (Disjoint-set)
25) Minimum Spanning Tree (Kruskal's Algorithm)
26) Sliding Window Technique
27) String Searching Using Rabin-Karp
28) Fenwick Tree (Binary Indexed Tree)
29) Dynamic Programming
30) Traveling Salesman Problem
Resources
Takeaways:
- 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 Main()
method:
As always, if you found any errors in this post please let me know!
CS Level Up Series (30 Part Series)
1) CS Level Up Series Introduction
2) Dynamic Arrays
3 ... 28
3) Linked Lists
4) Stacks
5) Queues
6) Hash Tables
7) Binary Search Trees
8) Binary Heaps
9) Priority Queues
10) Graphs
11) Tries
12) Binary & Bit Manipulation
13) Common Sorting Algorithms
14) Searching Algorithms
15) Permutations, Combinations, & Subsets
16) NP-Complete & Fibonacci Heap
17) Detecting Graph Cycles With Depth-First Search
18) Finding Shortest Paths In Graphs (using Dijkstra's & BFS)
19) Topological Sorting of Directed Acyclic Graphs (DAGs)
20) Finding Articulation Points & Bridges in Undirected Graphs
21) Finding Strongly Connected Components in Directed Graphs using Tarjan's Algorithm
22) Checking If An Undirected Graph Is Bipartite
23) Extending An Iterator
24) Union-find (Disjoint-set)
25) Minimum Spanning Tree (Kruskal's Algorithm)
26) Sliding Window Technique
27) String Searching Using Rabin-Karp
28) Fenwick Tree (Binary Indexed Tree)
29) Dynamic Programming
30) Traveling Salesman Problem
Discussion