Hello there, budding programmer! I hope you're ready because today, we're going to dive deep into high-level data manipulation and increase our understanding of heaps. Heaps are fundamental data structures commonly used in algorithms. We're going to leverage their potential today in an interesting algorithmic problem. Are you ready for the challenge? Let's get started!

We have a task at hand 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 to 1000, we need to create a Ruby method prefix_median. 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. And 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 half the sum of the middle two elements.

For example, consider an input array [1, 9, 2, 8, 3]. The output of your method should be [1, 5, 2, 5, 3].

Ruby provides several options to implement a heap through libraries like algorithms, which include heap data structures. In our task, we'll use these structures to manage our data efficiently.

In our context, we use a specific type of heap called a Min Heap, where the smallest element is located at the root. Additionally, we have a Max Heap, which stores the largest element at the root.

For our task, we'll be using these principal operations:

• Adding Elements: You can add a new element to a heap using the push method.

• Removing Elements: Use the pop method to remove and return the smallest or largest element from the heap.

• Accessing Minimum/Maximum Element: Use min or max to look at the smallest or largest element without removing it from the heap.

These operations ensure efficient organization and retrieval, allowing the smallest or largest element to be gathered quickly.

Alright, let's break our approach down into manageable steps. To begin with, we're going to need two heaps: a min heap to store the larger half of the numbers seen so far, and a max heap to store the smaller half. We'll also need an array to store the median for each prefix.

require 'algorithms' 

include Containers

def prefix_median(arr)
  min_heap = MinHeap.new
  max_heap = MaxHeap.new
  medians = []
end