C# PriorityQueue for Algorithmic Scheduling

This article explains how to implement algorithmic scheduling in C# using the PriorityQueue<TElement, TPriority> collection introduced in .NET 6. You will learn the core mechanics of the collection, how to configure it as a min-heap or max-heap, and how to apply it to a practical job scheduler that processes tasks based on scheduled execution times or priority levels.

Understanding PriorityQueue<TElement, TPriority>

The PriorityQueue<TElement, TPriority> class represents a collection of items that have a value and an associated priority. Internally, it is implemented as a array-backed quaternary (4-ary) min-heap. When dequeuing, the element with the lowest priority value is always removed first. Both Enqueue and Dequeue operations operate with \(O(\log n)\) time complexity.

By default:

• TElement: The data or task to be stored.
• TPriority: The criteria used to order elements (e.g., int, DateTime, TimeSpan).
• Min-Heap Behavior: The default comparer prioritizes smaller values (e.g., priority 1 is processed before priority 2, or an earlier DateTime before a later DateTime).

Basic Job Scheduling by Priority

In a traditional priority scheduler, tasks are assigned numeric ranks. The following example demonstrates scheduling jobs where lower numeric values indicate higher priority:

using System;
using System.Collections.Generic;

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

// Enqueue tasks: Enqueue(element, priority)
scheduler.Enqueue("Generate Daily Report", 3);
scheduler.Enqueue("Fix Critical Security Bug", 1);
scheduler.Enqueue("Respond to Customer Support", 2);
scheduler.Enqueue("Database Index Maintenance", 4);

// Process tasks in priority order
while (scheduler.TryDequeue(out string? task, out int priority))
{
    Console.WriteLine($"[Priority {priority}] Processing: {task}");
}

Output:

[Priority 1] Processing: Fix Critical Security Bug
[Priority 2] Processing: Respond to Customer Support
[Priority 3] Processing: Generate Daily Report
[Priority 4] Processing: Database Index Maintenance

Scheduling by Time (Earliest Deadline First)

To build a time-based scheduler (such as an Earliest Deadline First or delayed execution engine), use DateTime or DateTimeOffset as the TPriority type.

using System;
using System.Collections.Generic;
using System.Threading;
using System.Threading.Tasks;

public record ScheduledJob(string Id, Action Action);

public class TimeBasedScheduler
{
    private readonly PriorityQueue<ScheduledJob, DateTime> _queue = new();

    public void Schedule(ScheduledJob job, DateTime executionTime)
    {
        _queue.Enqueue(job, executionTime);
    }

    public async Task RunAsync(CancellationToken cancellationToken = default)
    {
        while (!cancellationToken.IsCancellationRequested)
        {
            if (_queue.TryPeek(out ScheduledJob? job, out DateTime executionTime))
            {
                var delay = executionTime - DateTime.UtcNow;

                if (delay <= TimeSpan.Zero)
                {
                    _queue.Dequeue();
                    job.Action();
                    continue;
                }

                // Wait until the next scheduled job is ready
                await Task.Delay(delay, cancellationToken);
            }
            else
            {
                // No jobs in queue; wait before checking again
                await Task.Delay(100, cancellationToken);
            }
        }
    }
}

Configuring Max-Heap Behavior

If your scheduling algorithm requires higher numeric values to be processed first, supply a custom IComparer<TPriority> to invert the comparison logic:

// Higher integer value executes first
var maxScheduler = new PriorityQueue<string, int>(Comparer<int>.Create((a, b) => b.CompareTo(a)));

maxScheduler.Enqueue("Low Priority Task", 10);
maxScheduler.Enqueue("Urgent Task", 100);

maxScheduler.TryDequeue(out string? urgentTask, out _);
// urgentTask resolves to "Urgent Task"

Key Considerations

• Thread Safety: PriorityQueue<TElement, TPriority> is not thread-safe. If multiple threads produce or consume tasks concurrently, synchronize access using a standard lock or wrap the operations inside a synchronization primitive.
• FIFO Tie-Breaking: The .NET PriorityQueue is not a stable priority queue. If two elements share the exact same priority, their dequeue order is non-deterministic. To enforce First-In, First-Out (FIFO) ordering for identical priorities, define a composite priority struct containing both the priority value and an incremental sequence number.