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.