Finding Prefix Medians Using Heaps in Ruby

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!

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