NeetCode - realestateexplorer/SystemDesign GitHub Wiki

explain priority queue, enqueue and dequeue in c#

---

Of course! Let's break down the Priority Queue concept and its key operations, Enqueue and Dequeue, specifically in the context of C#.

1. The Concept: What is a Priority Queue?

A Priority Queue is a special type of queue where each item has an associated "priority." Unlike a regular queue which operates on a "First-In, First-Out" (FIFO) basis, a priority queue dequeues items in order of their priority.

Think of an emergency room triage system:

• Regular Queue (like a deli counter): The first person to arrive is the first person served.
• Priority Queue (like an ER): A patient with a critical gunshot wound (high priority) will be seen before someone with a sprained ankle (low priority), even if the ankle sprain patient arrived first.

The item with the highest priority is always removed first.

Key Point in C#: The built-in PriorityQueue<TElement, TPriority> class in C# is a Min-Priority Queue. This means the item with the lowest priority value is considered the highest priority and will be dequeued first.

• Priority 1 comes out before priority 5.
• Priority 10 comes out before priority 100.

---

2. The C# Implementation: PriorityQueue<TElement, TPriority>

Starting with .NET 6, C# has a built-in, highly optimized PriorityQueue class in the System.Collections.Generic namespace.

It is defined as PriorityQueue<TElement, TPriority>, where:

• TElement: The type of the item you want to store (e.g., a string for a task name, a custom Patient object).
• TPriority: The type of the priority value, which must be comparable (e.g., int, double, DateTime).

// We will store strings (task names) with integer priorities.
// Lower integer means higher priority.
var taskQueue = new PriorityQueue<string, int>();

---

3. The Enqueue Operation

Purpose: To add a new item (an element and its priority) to the queue.

When you Enqueue an item, it isn't just added to the end. The Priority Queue internally reorganizes itself (typically using a data structure called a binary heap) to ensure that the item with the highest priority (lowest priority value) is ready to be accessed quickly.

How to use it: You call the .Enqueue() method, providing both the element and its priority.

Syntax: queue.Enqueue(TElement element, TPriority priority);

Enqueue Example:

Let's add some tasks to our queue in a non-sequential order of priority.

using System.Collections.Generic;

var taskQueue = new PriorityQueue<string, int>();

Console.WriteLine("Enqueuing tasks...");

// Enqueue tasks with their priorities (1 = highest priority)
taskQueue.Enqueue("Fix critical bug", 1);
taskQueue.Enqueue("Write documentation", 5);
taskQueue.Enqueue("Deploy to production", 2);
taskQueue.Enqueue("Add new feature", 3);

// At this point, the queue knows that "Fix critical bug" has the highest priority.
Console.WriteLine($"Number of tasks in queue: {taskQueue.Count}"); // Output: 4

---

4. The Dequeue Operation

Purpose: To remove the item with the highest priority from the queue and return it.

In C#'s Min-Priority Queue, Dequeue will always remove and return the element that has the lowest priority value.

Important: If you call Dequeue() on an empty queue, it will throw an InvalidOperationException. It's often safer to check queue.Count > 0 or use the TryDequeue() method.

Syntax: TElement element = queue.Dequeue();

Dequeue Example:

Continuing from the previous example, let's process the tasks. Notice how they come out in priority order, not the order they were added.

Console.WriteLine("\nProcessing tasks by priority...");

// Process tasks until the queue is empty
while (taskQueue.Count > 0)
{
    // Dequeue the highest-priority task
    string task = taskQueue.Dequeue();
    Console.WriteLine($"Processing: {task}");
}

Expected Output:

Enqueuing tasks...
Number of tasks in queue: 4

Processing tasks by priority...
Processing: Fix critical bug
Processing: Deploy to production
Processing: Add new feature
Processing: Write documentation

Putting It All Together: A Complete Example

This example demonstrates Enqueue, Dequeue, and the safer TryDequeue method.

using System;
using System.Collections.Generic;

// Let's model a hospital emergency room
public class Patient
{
    public string Name { get; set; }
    public Patient(string name) => Name = name;
}

public class PriorityQueueExample
{
    public static void Main(string[] args)
    {
        // TElement is Patient, TPriority is int
        // Priority 1: Critical, 2: Urgent, 3: Stable
        var erQueue = new PriorityQueue<Patient, int>();

        // Patients arrive in a random order
        Console.WriteLine("--- Patients Arriving ---");
        erQueue.Enqueue(new Patient("John (Broken Arm)"), 3);
        Console.WriteLine("Enqueued: John (Broken Arm), Priority 3");

        erQueue.Enqueue(new Patient("Alice (Chest Pains)"), 1);
        Console.WriteLine("Enqueued: Alice (Chest Pains), Priority 1");

        erQueue.Enqueue(new Patient("Bob (High Fever)"), 2);
        Console.WriteLine("Enqueued: Bob (High Fever), Priority 2");

        Console.WriteLine($"\nTotal patients in queue: {erQueue.Count}");

        Console.WriteLine("\n--- Doctors Treating Patients ---");
        // Use TryDequeue in a loop for safe processing
        while (erQueue.TryDequeue(out Patient patient, out int priority))
        {
            Console.WriteLine($"Treating patient: {patient.Name} with priority: {priority}");
        }

        Console.WriteLine($"\nPatients remaining in queue: {erQueue.Count}");
    }
}

Output of the Complete Example:

--- Patients Arriving ---
Enqueued: John (Broken Arm), Priority 3
Enqueued: Alice (Chest Pains), Priority 1
Enqueued: Bob (High Fever), Priority 2

Total patients in queue: 3

--- Doctors Treating Patients ---
Treating patient: Alice (Chest Pains) with priority: 1
Treating patient: Bob (High Fever) with priority: 2
Treating patient: John (Broken Arm) with priority: 3

Patients remaining in queue: 0

This output perfectly illustrates the core principle: despite arriving second, Alice was treated first because her priority value (1) was the lowest (i.e., the highest priority).

---