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 to 1000, we need to create a Python function prefix_median()
. This function will take the list as an 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. 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 list [1, 9, 2, 8, 3]
. The output of your function should be [1, 5.0, 2, 5.0, 3]
.
A Heap is a useful tool in Python that helps efficiently organize and retrieve data based on their values.
In our context, we use a specific type of heap called a Min Heap, where the smallest element is located at the beginning of our heap structure.
For our task, we'll be using these principal operations:
-
Adding Elements: You can add a new element to a heap using . This operation ensures the element is correctly positioned to maintain the Min Heap property.
