What is a Priority Queue and How Does it Work?
💡 Concept Name
Priority Queue – A special type of queue where each element is associated with a priority, and the element with the highest priority is served first.
📘 Quick Intro
Unlike a regular queue (FIFO), a priority queue serves elements based on their priority. It can be implemented using arrays, linked lists, heaps (commonly used), or binary search trees.
🧠 Analogy / Short Story
Imagine a hospital emergency room. Patients are treated based on the severity of their condition (priority), not on their arrival time. A patient with a heart attack will be treated before someone with a sprained ankle.
🔧 Technical Explanation
- 🔢 Each element has a priority value.
- ⬆️ Elements with higher priority are dequeued before lower priority ones.
- ⚖️ If two elements have the same priority, the order of insertion is used (FIFO).
- 🛠 Often implemented using a min-heap (lowest value = highest priority) or max-heap (highest value = highest priority).
- ⏱ Insert: O(log n), Remove: O(log n) using heaps.
🎯 Purpose & Use Case
- ✅ Task scheduling in operating systems.
- ✅ Dijkstra’s shortest path algorithm.
- ✅ Huffman encoding in compression.
- ✅ Managing bandwidth in routers (high priority packets).
💻 Real Code Example
public class PriorityQueueItem
{
public string Name { get; set; }
public int Priority { get; set; }
}
public class PriorityQueue
{
private List<PriorityQueueItem> queue = new();
public void Enqueue(string name, int priority)
{
queue.Add(new PriorityQueueItem { Name = name, Priority = priority });
queue = queue.OrderByDescending(x => x.Priority).ToList(); // Max priority first
}
public string Dequeue()
{
if (queue.Count == 0) return "Queue is empty";
var item = queue[0];
queue.RemoveAt(0);
return item.Name;
}
}
// Example usage
var pq = new PriorityQueue();
pq.Enqueue("Low Task", 1);
pq.Enqueue("High Task", 5);
Console.WriteLine(pq.Dequeue()); // Output: High Task
❓ Interview Q&A
Q1: What is a priority queue?
A: A data structure where each element has a priority, and elements are served based on priority rather than insertion order.
Q2: How is a priority queue different from a regular queue?
A: In a priority queue, elements with higher priority are dequeued before lower priority elements.
Q3: What are common implementations of priority queues?
A: Binary heaps, Fibonacci heaps, and balanced binary search trees.
Q4: What is the typical time complexity for insertion in a binary heap priority queue?
A: O(log n).
Q5: What is the time complexity for extracting the highest priority element?
A: O(log n).
Q6: Can priority queues handle elements with the same priority?
A: Yes, they can, usually served in insertion order or arbitrary order depending on implementation.
Q7: What are some applications of priority queues?
A: Task scheduling, Dijkstra’s shortest path algorithm, and Huffman coding.
Q8: What happens if a priority queue is implemented using an unsorted array?
A: Insertion is O(1) but extraction becomes O(n).
Q9: How does a max-heap represent a priority queue?
A: The root holds the highest priority element.
Q10: Are priority queues stable?
A: Not necessarily; stability depends on implementation.
📝 MCQs
Q1. What determines element order in a priority queue?
- Insertion order
- Element priority
- Alphabetical order
- Random order
Q2. How does a priority queue differ from a normal queue?
- Serves FIFO
- Serves highest priority first
- Random access
- LIFO order
Q3. What is a common implementation of priority queues?
- Array
- Linked list
- Binary heap
- Stack
Q4. What is insertion time complexity in a binary heap?
- O(1)
- O(log n)
- O(n)
- O(n log n)
Q5. What is extraction time complexity in a binary heap?
- O(1)
- O(log n)
- O(n)
- O(n log n)
Q6. Can priority queues handle duplicate priorities?
- No
- Yes
- Sometimes
- Never
Q7. Name an application of priority queues.
- Sorting
- Dijkstra's algorithm
- Hashing
- Searching
Q8. What is extraction complexity if using an unsorted array?
- O(1)
- O(log n)
- O(n)
- O(n log n)
Q9. In max-heap based priority queue, where is highest priority?
- At leaf
- At root
- Random
- Middle
Q10. Are priority queues always stable?
- Yes
- No
- Sometimes
- Depends on data
💡 Bonus Insight
.NET 6+ includes PriorityQueue<TElement, TPriority> in System.Collections.Generic, which simplifies working with priority queues using built-in types.
📄 PDF Download
Need a handy summary for your notes? Download this topic as a PDF!