Priority Queue Introduction and Concept in DSA C#

Mental Model

A priority queue is a special list where each item has a rank, and the highest rank item always comes out first.

Analogy: Imagine a line at a hospital emergency room where patients with more serious problems get treated before others, no matter when they arrived.

Priority Queue:
[5] -> [3] -> [4] -> [1] -> null
↑front (highest priority)

Dry Run Walkthrough

Input: Insert values 3, 5, 1, 4 into an empty priority queue and then remove the highest priority element.

Goal: Show how the queue keeps the highest priority (largest number) at the front and removes it first.

Step 1: Insert 3 into empty queue

[3] -> null ↑front

Why: First element becomes the front as it is the only one.

Step 2: Insert 5, which has higher priority than 3

[5] -> [3] -> null ↑front

Why: 5 moves to front because it has higher priority than 3.

Step 3: Insert 1, which has lower priority than front 5

[5] -> [3] -> [1] -> null ↑front

Why: 1 goes to the end because it has lowest priority.

Step 4: Insert 4, which fits between 5 and 3

[5] -> [4] -> [3] -> [1] -> null ↑front

Why: 4 is placed after 5 but before 3 to keep order by priority.

Step 5: Remove highest priority element (front)

[4] -> [3] -> [1] -> null ↑front

Why: Removing front 5 leaves 4 as new highest priority at front.

Result:

[4] -> [3] -> [1] -> null ↑front

Annotated Code

DSA C#

using System;

public class PriorityQueueNode
{
    public int Value;
    public PriorityQueueNode Next;

    public PriorityQueueNode(int value)
    {
        Value = value;
        Next = null;
    }
}

public class PriorityQueue
{
    private PriorityQueueNode front;

    public PriorityQueue()
    {
        front = null;
    }

    public void Enqueue(int value)
    {
        PriorityQueueNode newNode = new PriorityQueueNode(value);
        if (front == null || value > front.Value)
        {
            newNode.Next = front; // place new node before front
            front = newNode; // update front
            return;
        }

        PriorityQueueNode current = front;
        // find position to insert new node
        while (current.Next != null && current.Next.Value >= value)
        {
            current = current.Next; // move forward
        }

        newNode.Next = current.Next; // insert new node
        current.Next = newNode;
    }

    public int Dequeue()
    {
        if (front == null) throw new InvalidOperationException("Queue is empty");
        int value = front.Value;
        front = front.Next; // remove front
        return value;
    }

    public override string ToString()
    {
        PriorityQueueNode current = front;
        string result = "";
        while (current != null)
        {
            result += current.Value + " -> ";
            current = current.Next;
        }
        result += "null";
        return result;
    }
}

public class Program
{
    public static void Main()
    {
        PriorityQueue pq = new PriorityQueue();
        pq.Enqueue(3);
        pq.Enqueue(5);
        pq.Enqueue(1);
        pq.Enqueue(4);
        Console.WriteLine(pq.ToString());
        int removed = pq.Dequeue();
        Console.WriteLine($"Removed: {removed}");
        Console.WriteLine(pq.ToString());
    }
}

if (front == null || value > front.Value)

check if new value has highest priority to place at front

while (current.Next != null && current.Next.Value >= value)

find correct position to insert new node maintaining priority order

front = front.Next;

remove front node which has highest priority

Output

5 -> 4 -> 3 -> 1 -> null

Removed: 5

4 -> 3 -> 1 -> null

Complexity Analysis

Time: O(n) because in worst case we traverse the whole queue to insert in correct position

Space: O(n) because we store all elements in linked nodes

vs Alternative: Compared to a simple queue where insertion is O(1) at end, priority queue insertion is slower due to ordering but removal of highest priority is O(1)

Edge Cases

Empty queue

Enqueue adds first element as front; Dequeue throws exception

DSA C#

if (front == null || value > front.Value)

Insert element with priority equal to existing node

New element is placed after nodes with equal priority to maintain stable order

DSA C#

while (current.Next != null && current.Next.Value >= value)

Dequeue from empty queue

Throws InvalidOperationException to signal empty queue

DSA C#

if (front == null) throw new InvalidOperationException("Queue is empty");

When to Use This Pattern

When you need to always process the highest priority item first, use a priority queue because it keeps elements sorted by importance automatically.

Common Mistakes

Mistake: Inserting new elements at the end without sorting breaks priority order
Fix: Insert new elements in the correct position based on priority to maintain order

Mistake: Removing elements from the end instead of front loses priority guarantee
Fix: Always remove from the front where highest priority element is stored

Summary

A priority queue stores elements so the highest priority is always at the front.

Use it when you want to process important items before less important ones automatically.

The key is inserting elements in order so the front always holds the highest priority.

Practice

1. What is the main characteristic of a Priority Queue compared to a regular queue?

easy

A. Elements are dequeued in the exact order they were enqueued

B. Elements are dequeued based on their priority, not just order of insertion

C. It only stores elements of the same data type

D. It allows random access to elements by index

Solution

1. Step 1: Understand queue behavior

   A regular queue removes elements in the order they were added (FIFO).

2. Step 2: Understand priority queue behavior

   A priority queue removes elements based on priority, not just order.

3. Final Answer:

   Elements are dequeued based on their priority, not just order of insertion -> Option B

4. Quick Check:

   Priority queue = priority-based removal [OK]

Hint: Priority queue removes highest priority first, not oldest [OK]

Common Mistakes:

• Confusing priority queue with FIFO queue
• Thinking priority queue allows random access
• Assuming priority queue only stores one data type

2. Which of the following is the correct way to declare a priority queue of integers in C# using System.Collections.Generic.PriorityQueue?

easy

A. var pq = new PriorityQueue();

B. var pq = new PriorityQueue<int>();

C. PriorityQueue<int> pq = new PriorityQueue<>();

D. PriorityQueue pq = new PriorityQueue();

Solution

1. Step 1: Recall PriorityQueue syntax in C#

   The generic PriorityQueue requires two types: element type and priority type.

2. Step 2: Check each option

   var pq = new PriorityQueue(); correctly uses PriorityQueue<int, int>. Others have syntax errors or missing types.

3. Final Answer:

   var pq = new PriorityQueue(); -> Option A

4. Quick Check:

   PriorityQueue<TElement, TPriority> syntax [OK]

Hint: PriorityQueue needs element and priority types in angle brackets [OK]

Common Mistakes:

• Omitting priority type in generic declaration
• Using wrong constructor syntax
• Trying to declare without generic types

3. What will be the output of the following C# code?

var pq = new PriorityQueue();
pq.Enqueue("apple", 3);
pq.Enqueue("banana", 1);
pq.Enqueue("cherry", 2);
while (pq.Count > 0) {
    Console.Write(pq.Dequeue() + " ");
}

medium

A. banana cherry apple

B. apple cherry banana

C. cherry banana apple

D. apple banana cherry

Solution

1. Step 1: Understand enqueue priorities

   Elements are enqueued with priorities: apple=3, banana=1, cherry=2.

2. Step 2: Dequeue order based on priority

   PriorityQueue dequeues elements with lowest priority first: banana(1), cherry(2), apple(3).

3. Final Answer:

   banana cherry apple -> Option A

4. Quick Check:

   Lowest priority dequeued first = banana cherry apple [OK]

Hint: PriorityQueue dequeues lowest priority first by default [OK]

Common Mistakes:

• Assuming highest priority dequeued first
• Mixing element order with priority order
• Ignoring priority values

4. Identify the error in the following C# code using PriorityQueue:

var pq = new PriorityQueue();
pq.Enqueue(10, 2);
pq.Enqueue(5);
pq.Enqueue(20, 1);

medium

A. Enqueue method does not exist

B. PriorityQueue cannot store integers

C. PriorityQueue requires three generic types

D. Missing priority argument in second Enqueue call

Solution

1. Step 1: Check Enqueue method parameters

   Enqueue requires two arguments: element and priority.

2. Step 2: Identify incorrect call

   The second Enqueue call pq.Enqueue(5); misses the priority argument.

3. Final Answer:

   Missing priority argument in second Enqueue call -> Option D

4. Quick Check:

   Enqueue needs element and priority [OK]

Hint: Enqueue always needs element and priority arguments [OK]

Common Mistakes:

• Forgetting priority argument in Enqueue
• Thinking PriorityQueue needs three types
• Assuming Enqueue accepts one argument

5. You want to process tasks with priorities where higher numbers mean higher priority. How can you use C#'s PriorityQueue to dequeue tasks in order from highest to lowest priority?

hard

A. Use PriorityQueue as is; it dequeues highest priority first

B. Sort the queue manually after enqueueing

C. Store priorities as negative values when enqueuing

D. Use a Stack instead of PriorityQueue

Solution

1. Step 1: Understand PriorityQueue default behavior

   C# PriorityQueue dequeues elements with lowest priority first by default.

2. Step 2: Adjust priorities to reverse order

   To get highest priority first, store priorities as negative values (e.g., -priority).

3. Final Answer:

   Store priorities as negative values when enqueuing -> Option C

4. Quick Check:

   Invert priorities to reverse dequeue order [OK]

Hint: Invert priorities (negative) to get highest priority first [OK]

Common Mistakes:

• Assuming PriorityQueue dequeues highest priority first by default
• Trying to sort queue manually
• Using Stack which doesn't handle priorities