Solving Real-World Problems with Heaps in Python

Introduction

Welcome to this enriching session! Today, we will delve deeper into heaps by applying them to an intriguing real-world problem. 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.

Problem: Heap-based Median Finder

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 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.

Naive Approach and its Limitations

O(n \log n)

Efficient Approach

O(1)

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Implementing the Solution

Let's delve into the implementation specifics. We'll use Python's built-in module heapq, which allows us to create a standard min heap. By storing numbers as negatives, we can simulate a max heap.

First, we initialize two empty lists, which will serve as our heaps.

Python

import heapq
class MedianFinder:
    def __init__(self):
        self.heaps = [], []

import heapq
class MedianFinder:
    def __init__(self):
        self.heaps = [], []

addNum(num: int) -> None: When a new number arrives, we store the number in the large heap (MinHeap). We maintain the balance between the heaps by removing the smallest element from large and pushing it into small (our simulated max heap). If large has fewer elements than small, we balance it by pushing the largest element from small to large.

Python

    def addNum(self, num):
        small, large = self.heaps
        heapq.heappush(small, -heapq.heappushpop(large, num))
        if len(large) < len(small):
            heapq.heappush(large, -heapq.heappop(small))

    def addNum(self, num):
        small, large = self.heaps
        heapq.heappush(small, -heapq.heappushpop(large, num))
        if len(large) < len(small):
            heapq.heappush(large, -heapq.heappop(small))

findMedian() -> float: Finally, since large contains the larger elements, if large has more elements than small, the median is the smallest element in large. Otherwise, the median is the average of the smallest element in large and the largest in small.

Python

    def findMedian(self):
        small, large = self.heaps
        if len(large) > len(small):
            return float(large[0])
        # We subtract `small[0]` from `large[0]`, because `small` consists of negative values
        return float((large[0] - small[0]) / 2.0)

    def findMedian(self):
        small, large = self.heaps
        if len(large) > len(small):
            return float(large[0])
        # We subtract `small[0]` from `large[0]`, because `small` consists of negative values
        return float((large[0] - small[0]) / 2.0)

Solving Real-World Problems with Heaps in Python

Introduction

Problem: Heap-based Median Finder

Naive Approach and its Limitations

Efficient Approach

Join the 1M+ learners on CodeSignal

Implementing the Solution

Lesson Summary