Median of Data Stream Using Two Heaps in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to import the correct heap module for min heap operations.

DSA Python

import [1]

Drag options to blanks, or click blank then click option'

Amath

Bqueue

Cheapq

Dcollections

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'queue' instead of 'heapq' for heap operations.

Trying to implement heaps without importing any module.

The heapq module provides heap queue algorithms, which are used to implement min heaps in Python.

2fill in blank

medium

Complete the code to push a number into the max heap (using min heap with negated values).

DSA Python

import heapq

max_heap = []
num = 10
heapq.[1](max_heap, -num)

Drag options to blanks, or click blank then click option'

Apop

Bpush

Cheapify

Dheappush

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'push' which does not exist in heapq.

Using 'pop' which removes elements instead of adding.

The heappush function adds an element to the heap while maintaining the heap property.

3fill in blank

hard

Fix the error in the code to balance the two heaps after insertion.

DSA Python

if len(max_heap) > len(min_heap) + [1]:
    val = -heapq.heappop(max_heap)
    heapq.heappush(min_heap, val)

Drag options to blanks, or click blank then click option'

A1

B2

C0

D3

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 or 2 which causes incorrect balancing.

Not balancing heaps at all.

We balance heaps when the size difference is more than 1, so the correct number is 1.

4fill in blank

hard

Fill both blanks to correctly calculate the median when heaps have equal size.

DSA Python

if len(max_heap) == len(min_heap):
    median = (-max_heap[[1]] + min_heap[[2]]) / 2

Drag options to blanks, or click blank then click option'

A0

B1

C-1

D2

Attempts:

3 left

💡 Hint

Common Mistakes

Using index -1 for max_heap, confusing the heap root position.

Using index 1 or 2 which are out of heap root bounds.

The root of both heaps is at index 0. For max_heap (simulated min heap with negation), -max_heap[0] gives the maximum value of the left half; min_heap[0] gives the minimum value of the right half.

5fill in blank

hard

Fill all three blanks to insert a number and rebalance heaps correctly.

DSA Python

def add_num(num):
    if not max_heap or num <= -max_heap[0]:
        heapq.[1](max_heap, -num)
    else:
        heapq.[2](min_heap, num)

    if len(max_heap) > len(min_heap) + [3]:
        val = -heapq.heappop(max_heap)
        heapq.heappush(min_heap, val)

Drag options to blanks, or click blank then click option'

Aheappush

Bheappop

C1

Dheapreplace

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'heappop' to insert elements.

Using 'heapreplace' incorrectly here.

Rebalancing with wrong size difference.

We use heappush to add elements to heaps and rebalance when size difference is more than 1.

Practice

1. What is the main purpose of using two heaps (a max heap and a min heap) in the Median of Data Stream problem?

easy

A. To efficiently keep track of the lower half and upper half of the numbers for median calculation

B. To sort all numbers in ascending order

C. To store all numbers in one data structure

D. To remove duplicates from the data stream

Solution

1. Step 1: Understand the role of two heaps

   The max heap stores the smaller half of the numbers, and the min heap stores the larger half.

2. Step 2: Explain median calculation

   By balancing these heaps, the median can be found quickly from the top elements of the heaps.

3. Final Answer:

   To efficiently keep track of the lower half and upper half of the numbers for median calculation -> Option A

4. Quick Check:

   Two heaps split data halves = efficient median [OK]

Hint: Two heaps split data halves for quick median [OK]

Common Mistakes:

• Thinking heaps sort all data fully
• Using one heap only
• Confusing heaps with arrays

2. Which of the following Python code snippets correctly initializes the two heaps for the Median of Data Stream problem?

easy

A. max_heap = heapq.heapify([])
min_heap = heapq.heapify([])

B. max_heap = []
min_heap = []
max_heap = heapq.heapify(max_heap)
min_heap = heapq.heapify(min_heap)

C. max_heap = [] # will store negative values for max heap behavior
min_heap = []

D. max_heap = heapq.heapify([])
min_heap = []

Solution

1. Step 1: Understand heap initialization in Python

   Python's heapq module only supports min heaps, so to simulate a max heap, we store negative values in a list.

2. Step 2: Check code correctness

   max_heap = [] # will store negative values for max heap behavior min_heap = [] correctly initializes empty lists for both heaps; max heap will store negative values to simulate max heap behavior.

3. Final Answer:

   max_heap = [] # will store negative values for max heap behavior min_heap = [] -> Option C

4. Quick Check:

   Empty lists + negative values = max heap simulation [OK]

Hint: Use negative values in list for max heap in Python [OK]

Common Mistakes:

• Calling heapq.heapify on empty list returns None
• Trying to create max heap directly
• Confusing heapq.heapify return value

3. Given the following code snippet, what will be the output after inserting the numbers 5, 15, 1, 3 in order and then calling get_median()?

import heapq

class MedianFinder:
    def __init__(self):
        self.max_heap = []
        self.min_heap = []

    def add_num(self, num):
        if not self.max_heap or num <= -self.max_heap[0]:
            heapq.heappush(self.max_heap, -num)
        else:
            heapq.heappush(self.min_heap, num)

        if len(self.max_heap) > len(self.min_heap) + 1:
            heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap))
        elif len(self.min_heap) > len(self.max_heap):
            heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap))

    def get_median(self):
        if len(self.max_heap) > len(self.min_heap):
            return float(-self.max_heap[0])
        else:
            return (-self.max_heap[0] + self.min_heap[0]) / 2

finder = MedianFinder()
for number in [5, 15, 1, 3]:
    finder.add_num(number)
print(finder.get_median())

medium

A. 3.0

B. 6.0

C. 5.0

D. 4.0

Solution

1. Step 1: Insert numbers and balance heaps

   Insert 5: max_heap=[-5], min_heap=[]; median=5 Insert 15: max_heap=[-5], min_heap=[15]; median=(5+15)/2=10 Insert 1: max_heap=[-5,-1], min_heap=[15]; median=5 Insert 3: max_heap=[-3,-1], min_heap=[5,15]; median=(3+5)/2=4.0

2. Step 2: Calculate final median

   After all insertions, median is 4.0 as heaps are balanced and median is average of tops.

3. Final Answer:

   4.0 -> Option D

4. Quick Check:

   Median after 4 inserts = 4.0 [OK]

Hint: Balance heaps and average tops for even count [OK]

Common Mistakes:

• Not balancing heaps after insertion
• Forgetting to invert max heap values
• Calculating median incorrectly for even count

4. The following code snippet is intended to add a number to the MedianFinder class but contains a bug. What is the bug?

def add_num(self, num):
    if not self.max_heap or num < -self.max_heap[0]:
        heapq.heappush(self.max_heap, -num)
    else:
        heapq.heappush(self.min_heap, num)

    if len(self.max_heap) > len(self.min_heap):
        heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap))
    elif len(self.min_heap) > len(self.max_heap) + 1:
        heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap))

medium

A. The balancing conditions are reversed; max_heap can grow too large

B. The comparison should be <= instead of < in the first if condition

C. The heaps are not initialized before use

D. The code uses min heap for max_heap without negation

Solution

1. Step 1: Analyze balancing conditions

   The code moves elements when max_heap size > min_heap size, but it should allow max_heap to be larger by at most 1.

2. Step 2: Identify correct balancing logic

   Correct logic: if max_heap size > min_heap size + 1, move element to min_heap; if min_heap size > max_heap size, move element to max_heap.

3. Final Answer:

   The balancing conditions are reversed; max_heap can grow too large -> Option A

4. Quick Check:

   Balance heaps with correct size difference [OK]

Hint: Max heap can be bigger by only 1 element [OK]

Common Mistakes:

• Swapping balancing conditions
• Not allowing max_heap to be bigger by one
• Incorrect comparison operators

5. You want to extend the MedianFinder to support removing numbers from the data stream while still efficiently calculating the median. Which data structure modification is best to support this feature?

hard

A. Keep using two heaps and rebuild them after each removal

B. Use balanced binary search trees (like AVL or Red-Black trees) instead of heaps

C. Use a single sorted list and binary search for insertion and removal

D. Use hash maps to store counts and ignore heaps

Solution

1. Step 1: Understand removal challenges with heaps

   Heaps do not support efficient arbitrary removal; rebuilding heaps after each removal is costly.

2. Step 2: Identify suitable data structure

   Balanced binary search trees support insertion, removal, and median retrieval in O(log n) time.

3. Step 3: Compare other options

   Sorted lists have O(n) removal; hash maps do not maintain order; rebuilding heaps is inefficient.

4. Final Answer:

   Use balanced binary search trees (like AVL or Red-Black trees) instead of heaps -> Option B

5. Quick Check:

   Balanced BSTs support fast insert/remove/median [OK]

Hint: Balanced trees allow fast insert and remove [OK]

Common Mistakes:

• Assuming heaps support fast removal
• Using sorted lists with slow removal
• Ignoring order maintenance