C# Priority Queue

Imagine a heap as a special kind of tree where each parent node has a value that's less than or equal to the values of its children. In simpler terms, you can think of it as a tree where the parent node is always smaller (or larger) than its children. This property makes heaps perfect for priority queues, where the topmost element (root) always has the highest (or lowest) priority.

By default, the .NET class PriorityQueue provide us with a Min Heap. This means that the smallest element is always at the root (every parent node has a value less than or equal to the values of its children), however, we are allowed to pass a "Comparer" function to modify this behavior.

This is what I want to show you in this article. We are going to implement a Max Heap using the Priority Queue class, introduced in .NET 6

We will resolve this leetcode exercise:

You are given a positive integer num. You may swap any two digits of num that have the same parity (i.e. both odd digits or both even digits).

Return the largest possible value of num after any number of swaps.

Solution: This method initializes two priority queues, pqOdd and pqEven, to store odd and even digits respectively in descending order. It then iterates through each digit of the input number, enqueuing them into the appropriate priority queue based on their parity (odd or even) and marking their position in the result list accordingly. After all digits are processed, it dequeues the digits from the priority queues in the order specified by the result list, effectively rearranging them to form the largest integer possible. Finally, it converts the rearranged digits back into an integer and returns it.

Note that we pass a Comparer function and therefore achieve the behavior of the priority queue as a max heap

public class Solution
{
    // Method to find the largest possible integer by rearranging the digits of the input number
    public int LargestInteger(int num)
    {
        // Initialize two priority queues to store digits: pqOdd for odd digits and pqEven for even digits
        // Priority queues are initialized with custom comparers to ensure descending order
        PriorityQueue<int, int> pqOdd = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b - a));
        PriorityQueue<int, int> pqEven = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b - a));

        // List to store the result digits
        List<int> result = new List<int>();

        // Iterate through each digit of the input number
        foreach (char digit in num.ToString())
        {
            // Convert the character digit to an integer
            int digitInt = int.Parse(digit.ToString());

            // Check if the digit is even or odd
            if (digitInt % 2 == 0) {
                // If even, enqueue the digit into pqOdd with the digit itself as priority
                pqOdd.Enqueue(digitInt, digitInt);
                // Add 0 to the result list to mark the position of the even digit
                result.Add(0);
            }
            else {
                // If odd, enqueue the digit into pqEven with the digit itself as priority
                pqEven.Enqueue(digitInt, digitInt);
                // Add 1 to the result list to mark the position of the odd digit
                result.Add(1);
            };
        }

        // Iterate through the result list to rearrange the digits
        for (int i = 0; i < result.Count(); i++)
        {
            // If the result at index i is 0, dequeue the top element from pqOdd and update the result list
            if (result[i] == 0)
            {
                result[i] = pqOdd.Dequeue();
            }
            // If the result at index i is 1, dequeue the top element from pqEven and update the result list
            else
            {
                result[i] = pqEven.Dequeue();
            }
        }

        // Convert the result list to a string and then to an integer, and return it
        return int.Parse(string.Join("", result));
    }
}