loading...

Priority Queues

jjb profile image JB Updated on ・2 min read

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

  1. Priority Queue Overview
  2. Short paragraph overview/why to use binary heap for implementation

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

Posted on Nov 27 '19 by:

Discussion

markdown guide