Using Heaps in C++ to Calculate Prefix Medians

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

Remember that a prefix of a vector 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 vector {1, 9, 2, 8, 3}. The output of your function should be {1, 1, 2, 2, 3}.

A heap is a useful tool in C++ that helps efficiently organize and retrieve data based on their values.

In our context, we use two specific types of heaps: a Min Heap and a Max Heap. The Min Heap is used to store the larger half of the numbers seen so far, while the Max Heap stores the smaller half. In C++, heaps are implemented as priority_queue containers.

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. By default, C++'s priority_queue is a Max Heap. To create a Min Heap, you need to use a custom comparator like greater<int>. This ensures that the smallest element is always at the top.

  C++

  std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

• Removing Elements: The pop() method removes the top element from the heap, which is the smallest element in the Min Heap or the largest element in the Max Heap.

• Accessing Minimum Element: The top() method is used to inspect the root element of the heap without removing it. For the Min Heap with a greater<int> comparator, top() will return the smallest element.

These operations ensure that the root element can always be gathered quickly, in constant time $O(1)$, and new elements can be added while maintaining the heap structure in logarithmic time, $O(log n)$.