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));
}
}
Top comments (0)