Efficient Array Manipulation with Heaps in C#

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 index 2 * 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:

public class MinHeap {
    private List<int> heap;

    public MinHeap() {
        heap = new List<int>();
    }

    public void Add(int value) {
        heap.Add(value);
        HeapifyUp(heap.Count - 1);
    }

    public int Poll() {
        if (heap.Count == 0) return -1;
        if (heap.Count == 1) {
            int root = heap[0];
            heap.RemoveAt(0);
            return root;
        }
        int result = heap[0];
        heap[0] = heap[heap.Count - 1];
        heap.RemoveAt(heap.Count - 1);
        HeapifyDown(0);
        return result;
    }

    public int Peek() {
        return heap[0];
    }

    public int Size() {
        return heap.Count;
    }

    private void HeapifyUp(int index) {
        while (index > 0 && heap[index] < heap[(index - 1) / 2]) {
            int parentIndex = (index - 1) / 2;
            Swap(index, parentIndex);
            index = parentIndex;
        }
    }

    private void HeapifyDown(int index) {
        int leftChild, rightChild, smallestChild;
        
        while (index * 2 + 1 < heap.Count) {
            leftChild = index * 2 + 1;
            rightChild = index * 2 + 2;
            smallestChild = leftChild;
            
            if (rightChild < heap.Count && heap[rightChild] < heap[leftChild]) {
                smallestChild = rightChild;
            }

            if (heap[index] <= heap[smallestChild]) {
                break;
            }

            Swap(index, smallestChild);
            index = smallestChild;
        }
    }

    private void Swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }
}

public class MaxHeap : MinHeap {
    public new void Add(int value) {
        base.Add(-value);
    }

    public new int Poll() {
        return -base.Poll();
    }

    public new int Peek() {
        return -base.Peek();
    }
}

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.