Prefix Medians with Heaps

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 a list of unique integers with elements ranging from 1 to 10^6 and length between 1 and 1000, we need to create a Scala function prefixMedian. This function will take the list as input and return a corresponding list, which consists of the medians of all the prefixes of the input list.

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 half the sum of the middle two elements.

For example, consider an input list List(1, 9, 2, 8, 3). The output of your function should be List(1, 5.0, 2, 5.0, 3).

A heap is a complete binary tree where each parent node has a specific relationship with its children based on their values. This relationship, called the heap property, defines two types of heaps:

• Max-Heap: Every parent node's value is greater than or equal to its children's values. This means the largest element is always at the root (top) of the tree.
• Min-Heap: Every parent node's value is less than or equal to its children's values. This means the smallest element is always at the root (top) of the tree.

For example, in a max-heap containing the values [10, 8, 6, 4, 2], the value 10 would be at the root since it's the largest. The remaining values (8, 6, 4, 2) could be arranged in various ways as long as each parent is greater than or equal to its children.

For our median-finding task, heaps are particularly useful because they allow us to efficiently maintain two sorted halves of our data and quickly access the middle elements needed to calculate medians.

In Scala, we use the PriorityQueue class to efficiently access the minimum or maximum element from a collection. PriorityQueue achieves this efficiency by using heap implementation internally. By default, PriorityQueue in Scala behaves as a max-heap, meaning the largest element is always at the front. To create min-heap behavior, we can use a custom ordering that reverses the default order.

For our task, we'll use two heaps:

• Min Heap: Stores the larger half of the numbers seen so far. We create this by using a PriorityQueue with the default ordering reversed.
• Max Heap: Stores the smaller half of the numbers seen so far. We use the default PriorityQueue for this.

The principal operations we'll use are:

• Adding Elements: Use enqueue to add a new element to a heap. The heap will automatically maintain its property.
• Removing Elements: Use dequeue to remove and return the top element from the heap.
• Accessing the Top Element: Use head to inspect the top element without removing it.

These operations ensure that the largest (for max-heap) or smallest (for min-heap) element can always be accessed quickly, and new elements can be added efficiently.