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!

📄 PDF Download Coming Soon