Median of Data Stream Using Two Heaps in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind using two heaps to find the median of a data stream?

Use a max heap to store the smaller half of numbers and a min heap to store the larger half. This way, the median is either the top of one heap or the average of the tops of both heaps.

beginner

Why do we balance the sizes of the two heaps when finding the median?

Balancing ensures that the heaps differ in size by at most one, so the median can be found easily from the top elements of the heaps.

beginner

In the two heaps approach, which heap stores the smaller half of the numbers?

The max heap stores the smaller half of the numbers, so its top is the largest of the smaller half.

intermediate

How do you find the median if the total number of elements is odd using two heaps?

The median is the top element of the heap that has one extra element (either max heap or min heap).

intermediate

What is the time complexity of adding a number and finding the median using two heaps?

Adding a number takes O(log n) due to heap insertion, and finding the median is O(1) because it involves looking at the top elements.

Which heap stores the larger half of the numbers in the two heaps approach?

A Max heap

B Both heaps store the same numbers

C Neither heap stores the larger half

D Min heap

The min heap stores the larger half of the numbers so its top is the smallest of the larger half.

What do you do if the max heap has two more elements than the min heap after insertion?

A Remove the top from max heap and add it to min heap

B Remove the top from min heap and add it to max heap

C Do nothing

D Remove the smallest element from both heaps

To balance, move the largest element from max heap to min heap.

If the total number of elements is even, how is the median calculated?

A Average of tops of max heap and min heap

B Top of min heap

C Top of max heap

D Sum of all elements divided by total count

Median is the average of the largest of smaller half and smallest of larger half.

What is the main advantage of using two heaps for median of data stream?

A Constant time insertion

B Constant time median retrieval

C No need to sort all elements every time

D Uses less memory

Two heaps avoid sorting the entire data stream on each insertion.

Which operation is more expensive when using two heaps: insertion or finding median?

A Neither operation is expensive

B Insertion

C Both are equally expensive

D Finding median

Insertion involves heap operations O(log n), while median retrieval is O(1).

Explain how two heaps are used to maintain the median in a data stream.

Think about splitting numbers into two groups and how to keep track of the middle.

Describe the steps to add a new number to the two heaps and update the median.

Consider where the new number fits and how to keep heaps balanced.

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 sort all numbers in ascending order

B. To store all numbers in a single data structure

C. To efficiently keep track of the lower half and upper half of the numbers separately

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 how this helps find the median

   By balancing these heaps, the median is either the top of one heap or the average of tops of both heaps.

3. Final Answer:

   To efficiently keep track of the lower half and upper half of the numbers separately -> Option C

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 numbers fully
• Using one heap only
• Confusing heaps with arrays

2. Which TypeScript syntax correctly declares a max heap using a priority queue for numbers?

easy

A. const maxHeap = new PriorityQueue<number>((a, b) => b - a);

B. const maxHeap = new PriorityQueue<number>((a, b) => a - b);

C. const maxHeap = new PriorityQueue<number>();

D. const maxHeap = new PriorityQueue<number>((a, b) => a + b);

Solution

1. Step 1: Understand max heap comparator

   Max heap comparator returns positive if first is less than second, so b - a creates max heap.

2. Step 2: Check each option

   const maxHeap = new PriorityQueue<number>((a, b) => b - a); uses (b - a) which is correct for max heap; others do not create max heap order.

3. Final Answer:

   const maxHeap = new PriorityQueue<number>((a, b) => b - a); -> Option A

4. Quick Check:

   Comparator b - a = max heap [OK]

Hint: Max heap comparator subtracts first from second [OK]

Common Mistakes:

• Using a - b for max heap (creates min heap)
• Not providing comparator
• Using addition in comparator

3. Given the following sequence of numbers inserted into the data stream: [5, 15, 1, 3], what is the median after all insertions using two heaps?

medium

A. 3

B. 4

C. 5

D. 8

Solution

1. Step 1: Insert numbers and balance heaps

   Insert 5 -> maxHeap=[5] (top=5), minHeap=[]; Insert 15 -> minHeap=[15] (top=15), sizes 1:1; Insert 1 -> maxHeap=[5,1] (top=5), sizes 2:1; Insert 3 -> maxHeap=[5,3,1] (top=5), sizes 3:1 -> balance (max.size > min.size+1), move max.top=5 to minHeap -> maxHeap=[3,1] (top=3), minHeap=[5,15] (top=5), sizes 2:2.

2. Step 2: Calculate median from heaps

   Sizes equal, median = (maxHeap.top + minHeap.top)/2 = (3 + 5)/2 = 4.

3. Final Answer:

   4 -> Option B

4. Quick Check:

   Median of [5,15,1,3] = 4 [OK]

Hint: Median is average of two heap tops if sizes equal [OK]

Common Mistakes:

• Taking median as top of one heap only
• Not balancing heaps after insertion
• Wrong average calculation

4. Consider this TypeScript snippet for adding a number to the data stream median finder:

if (num <= maxHeap.peek()) {
  maxHeap.enqueue(num);
} else {
  minHeap.enqueue(num);
}

// Balance heaps
if (maxHeap.size() > minHeap.size() + 1) {
  minHeap.enqueue(maxHeap.dequeue());
} else if (minHeap.size() > maxHeap.size()) {
  maxHeap.enqueue(minHeap.dequeue());
}

What is the bug in this code?

medium

A. It compares num with minHeap.peek() instead of maxHeap.peek()

B. It balances heaps incorrectly by moving elements the wrong way

C. It uses enqueue instead of push for heaps

D. It does not handle empty maxHeap before peek() call

Solution

1. Step 1: Analyze peek() usage on maxHeap

   If maxHeap is empty, calling peek() causes error because no element exists yet.

2. Step 2: Identify missing empty check

   Code should check if maxHeap is empty before peek() or handle initial insertion separately.

3. Final Answer:

   It does not handle empty maxHeap before peek() call -> Option D

4. Quick Check:

   Empty heap peek() causes runtime error [OK]

Hint: Check heap empty before peek() to avoid errors [OK]

Common Mistakes:

• Assuming heaps always have elements
• Mixing enqueue and push methods
• Balancing heaps incorrectly

5. You want to extend the Median of Data Stream solution to support removing numbers from the stream efficiently. Which data structure modification is best to support both insertion and removal while maintaining median calculation?

hard

A. Use two heaps with a hash map to mark removed elements lazily

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

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

D. Use two queues to store lower and upper halves

Solution

1. Step 1: Understand removal challenge in heaps

   Heaps do not support efficient arbitrary removal, so direct removal is costly.

2. Step 2: Explain lazy removal with hash map

   Mark elements as removed in a hash map and skip them during heap operations to simulate removal efficiently.

3. Step 3: Compare other options

   Balanced trees support removal but are more complex; arrays are inefficient; queues do not maintain order.

4. Final Answer:

   Use two heaps with a hash map to mark removed elements lazily -> Option A

5. Quick Check:

   Lazy removal with hash map + heaps = efficient median update [OK]

Hint: Lazy removal with hash map keeps heaps efficient [OK]

Common Mistakes:

• Trying direct removal from heaps
• Using arrays causing slow operations
• Ignoring complexity of balanced trees