Hello there, aspiring C# developer! I hope you're ready because today we're going to delve into high-level data manipulation and increase our understanding of heaps in C#. Heaps are fundamental data structures that play a significant role in various algorithms. Today, we'll unlock their potential in an intriguing algorithmic problem. Are you ready for the challenge? Let's get started!
We have a task related to array manipulation and the use of heaps. The task is as follows: Given an array of unique integers with elements ranging from 1 to (10^6) and a length between 1 and 1000, we need to create a C# method PrefixMedian(). This method will take the array as input and return a corresponding array, which consists of the medians of all the prefixes of the input array.
Remember that a prefix of an array is a contiguous subsequence that starts from the first element. The median of a sequence of numbers is the middle number when the sequence is sorted. If the length of the sequence is even, the median is the element in the position length / 2 - 1.
For example, consider an input array [1, 9, 2, 8, 3]. The output of your method should be [1, 1, 2, 2, 3].
In C#, a heap is a sophisticated, binary tree-based data structure designed with the heap property in mind: for a Min Heap, every parent node’s value is less than or equal to its children, while for a Max Heap, each parent node's value is greater than or equal to its children. These properties make heaps ideal for efficiently finding and removing the minimum or maximum elements.
Heaps are often implemented using arrays, where the tree structure is mapped as follows:
- For any node located at index
i, its left child is at index2 * i + 1 - The right child is at
2 * i + 2 - Its parent is located at
Math.Floor((i - 1) / 2)
In this context, we use two types of heaps:
- Min Heap: Holds the larger half of the numbers seen so far.
- Max Heap: Holds the smaller half.
C# doesn't come with built-in heap functionality, so we implemented one using lists.
Here are custom implementations for MinHeap and MaxHeap using lists:
C#1public class MinHeap { 2 private List<int> heap; 3 4 public MinHeap() { 5 heap = new List<int>(); 6 } 7 8 public void Add(int value) { 9 heap.Add(value); 10 HeapifyUp(heap.Count - 1); 11 } 12 13 public int Poll() { 14 if (heap.Count == 0) return -1; 15 if (heap.Count == 1) { 16 int root = heap[0]; 17 heap.RemoveAt(0); 18 return root; 19 } 20 int result = heap[0]; 21 heap[0] = heap[heap.Count - 1]; 22 heap.RemoveAt(heap.Count - 1); 23 HeapifyDown(0); 24 return result; 25 } 26 27 public int Peek() { 28 return heap[0]; 29 } 30 31 public int Size() { 32 return heap.Count; 33 } 34 35 private void HeapifyUp(int index) { 36 while (index > 0 && heap[index] < heap[(index - 1) / 2]) { 37 int parentIndex = (index - 1) / 2; 38 Swap(index, parentIndex); 39 index = parentIndex; 40 } 41 } 42 43 private void HeapifyDown(int index) { 44 int leftChild, rightChild, smallestChild; 45 46 while (index * 2 + 1 < heap.Count) { 47 leftChild = index * 2 + 1; 48 rightChild = index * 2 + 2; 49 smallestChild = leftChild; 50 51 if (rightChild < heap.Count && heap[rightChild] < heap[leftChild]) { 52 smallestChild = rightChild; 53 } 54 55 if (heap[index] <= heap[smallestChild]) { 56 break; 57 } 58 59 Swap(index, smallestChild); 60 index = smallestChild; 61 } 62 } 63 64 private void Swap(int i, int j) { 65 int temp = heap[i]; 66 heap[i] = heap[j]; 67 heap[j] = temp; 68 } 69} 70 71public class MaxHeap : MinHeap { 72 public new void Add(int value) { 73 base.Add(-value); 74 } 75 76 public new int Poll() { 77 return -base.Poll(); 78 } 79 80 public new int Peek() { 81 return -base.Peek(); 82 } 83}
The MinHeap class offers operations like Add (insert element), Poll (remove and return the smallest element), Peek (look at the smallest element), and Size (get heap size). The HeapifyUp and HeapifyDown methods ensure the heap property is maintained. The MaxHeap class relies on MinHeap, but manipulates negated values to handle max-heap operations by overriding methods to negate values, converting its behavior.
We first set up our maxHeap and minHeap for storing smaller and larger halves, respectively, and an array to store medians:
C#1public class Solution { 2 public static int[] PrefixMedian(int[] arr) { 3 MinHeap minHeap = new MinHeap(); 4 MaxHeap maxHeap = new MaxHeap(); 5 int[] medians = new int[arr.Length]; 6 7 return medians; 8 } 9}
Next, as we iterate through the array, we decide whether to insert each element into the maxHeap or minHeap based on its value:
C#1public class Solution { 2 public static int[] PrefixMedian(int[] arr) { 3 MinHeap minHeap = new MinHeap(); 4 MaxHeap maxHeap = new MaxHeap(); 5 int[] medians = new int[arr.Length]; 6 7 foreach (int num in arr) { 8 if (maxHeap.Size() > 0 && num < maxHeap.Peek()) { 9 maxHeap.Add(num); 10 } else { 11 minHeap.Add(num); 12 } 13 } 14 15 return medians; 16 } 17}
To ensure we can access medians efficiently, we need to balance the heaps. If maxHeap becomes larger, we transfer elements, and if minHeap is larger by more than one, we transfer elements back:
C#1public class Solution { 2 public static int[] PrefixMedian(int[] arr) { 3 MinHeap minHeap = new MinHeap(); 4 MaxHeap maxHeap = new MaxHeap(); 5 int[] medians = new int[arr.Length]; 6 7 for (int i = 0; i < arr.Length; i++) { 8 int num = arr[i]; 9 if (maxHeap.Size() > 0 && num < maxHeap.Peek()) { 10 maxHeap.Add(num); 11 } else { 12 minHeap.Add(num); 13 } 14 15 if (maxHeap.Size() > minHeap.Size()) { 16 minHeap.Add(maxHeap.Poll()); 17 } else if (minHeap.Size() > maxHeap.Size() + 1) { 18 maxHeap.Add(minHeap.Poll()); 19 } 20 } 21 22 return medians; 23 } 24}
Finally, the medians are extracted, where equality of heap sizes leads to picking from maxHeap's root, and otherwise from minHeap:
C#1public class Solution { 2 public static int[] PrefixMedian(int[] arr) { 3 MinHeap minHeap = new MinHeap(); 4 MaxHeap maxHeap = new MaxHeap(); 5 int[] medians = new int[arr.Length]; 6 7 for (int i = 0; i < arr.Length; i++) { 8 int num = arr[i]; 9 if (maxHeap.Size() > 0 && num < maxHeap.Peek()) { 10 maxHeap.Add(num); 11 } else { 12 minHeap.Add(num); 13 } 14 15 if (maxHeap.Size() > minHeap.Size()) { 16 minHeap.Add(maxHeap.Poll()); 17 } else if (minHeap.Size() > maxHeap.Size() + 1) { 18 maxHeap.Add(minHeap.Poll()); 19 } 20 21 medians[i] = (minHeap.Size() == maxHeap.Size()) ? maxHeap.Peek() : minHeap.Peek(); 22 } 23 24 return medians; 25 } 26 27 public static void Main() { 28 int[] arr = {1, 9, 2, 8, 3}; 29 int[] medians = PrefixMedian(arr); 30 Console.WriteLine("Final Medians Array: "); 31 foreach (int median in medians) { 32 Console.Write(median + " "); 33 } 34 } 35}
This C# implementation balances the heaps and extracts prefixes' medians effectively, building an array of medians that is printed in the Main method.
Congratulations! You've successfully tackled an engaging algorithmic problem that required the use of heaps for array manipulation in C#. By creating and managing your heap data structure, you reinforced your understanding of both C# data management and algorithmic problem-solving. Keep practicing with similar problems to strengthen your grasp of heaps and array manipulations. Remember — consistency and practice lead to mastery. Happy coding!