Welcome to this enriching session! Today, we will delve deeper into heaps by applying them to two intriguing problems. This will help you understand how heaps, a form of tree structure, can create efficient solutions to practical problems. Before we begin, remember that heaps are a type of priority queue where parent nodes always have values lesser (in a Min Heap) or greater (in a Max Heap) than their child nodes. This property is the foundation of our problem-solving approach with heaps.
Consider this scenario: You're working on an algorithm for a real-time analytics engine that calculates the median value of a continuously growing dataset. For instance, an ad tech company might need to analyze click-stream data in real time. Our first problem is to create a data structure that supports adding a number while ensuring efficient retrieval of the median at any given point.
Note: A median value is the middle number in a data set when arranged in ascending order. If there is an even number of data points, the median is the average of the two numbers in the middle. It is a measure of central tendency used in statistics.
One initial approach could be to save each incoming number in a Python list. Whenever we need the median, we can sort the list and compute it. However, as the list length increases, the time to sort the list also grows as sorting has a time complexity of per each median search request. Thus, this approach becomes less efficient when we want to add and retrieve the median frequently.
