Median of Data Stream Using Two Heaps in DSA Javascript - 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.

beginner

How do you find the median when the total number of elements is even using two heaps?

The median is the average of the top elements of the max heap and the 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) since it involves only the top elements of the heaps.

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

A Max heap

B Both heaps store equal halves

C Min heap

D None of the above

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 more than one extra element compared to the min heap?

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 Clear both heaps

To balance the heaps, move the top element from the larger max heap to the min heap.

If the total number of elements is odd, where is the median found?

A Top of max heap

B Top of min heap

C Average of tops of both heaps

D Bottom of max heap

When odd, the max heap has one extra element, so the median is its top.

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

A Faster sorting of all elements

B Efficient insertion and median retrieval without sorting all data

C Less memory usage

D No need to balance heaps

Two heaps allow efficient insertion and quick median retrieval without sorting the entire data.

Which operation is NOT needed when adding a new number to the two heaps?

A Compare with max heap top

B Insert into one of the heaps

C Balance the heaps if needed

D Sort all elements

Sorting all elements is not needed; heaps maintain order efficiently.

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

Think about splitting numbers into two groups and how to find the middle.

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

Focus on where to put the new number and how to keep heaps balanced.

Practice

1. What is the main purpose of using two heaps (a max-heap and a min-heap) when finding the median of a data stream?

easy

A. To sort all numbers in ascending order

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

C. To store all numbers in a single data structure

D. To find the maximum number in 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 the tops of both heaps.

3. Final Answer:

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

4. Quick Check:

   Two heaps split data halves = A [OK]

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

Common Mistakes:

• Thinking heaps sort all numbers fully
• Using only one heap for median
• Confusing max-heap and min-heap roles

2. Which of the following is the correct way to insert a number into the two heaps when maintaining the median in JavaScript?

easy

A. Always insert into min-heap

B. Always insert into max-heap

C. Insert into max-heap if number is less than or equal to max-heap root; else insert into min-heap

D. Insert randomly into either heap

Solution

1. Step 1: Decide heap based on number value

   If the number is smaller or equal to the max-heap root, it belongs to the lower half, so insert into max-heap.

2. Step 2: Otherwise insert into min-heap

   If the number is greater, it belongs to the upper half, so insert into min-heap.

3. Final Answer:

   Insert into max-heap if number is less than or equal to max-heap root; else insert into min-heap -> Option C

4. Quick Check:

   Compare with max-heap root to choose heap [OK]

Hint: Compare with max-heap root to choose heap [OK]

Common Mistakes:

• Inserting all numbers into one heap
• Not comparing with max-heap root
• Inserting randomly without condition

3. Consider the following JavaScript code snippet using two heaps to find the median after inserting numbers 5, 15, 1, 3:

const maxHeap = new MaxHeap();
const minHeap = new MinHeap();

function addNum(num) {
  if (maxHeap.size() === 0 || num <= maxHeap.peek()) {
    maxHeap.insert(num);
  } else {
    minHeap.insert(num);
  }

  if (maxHeap.size() > minHeap.size() + 1) {
    minHeap.insert(maxHeap.extract());
  } else if (minHeap.size() > maxHeap.size()) {
    maxHeap.insert(minHeap.extract());
  }
}

addNum(5);
addNum(15);
addNum(1);
addNum(3);

const median = maxHeap.size() > minHeap.size() ? maxHeap.peek() : (maxHeap.peek() + minHeap.peek()) / 2;
console.log(median);

What is the output printed?

medium

A. 4

B. 3

C. 5

D. 6

Solution

1. Step 1: Insert numbers and balance heaps

   Insert 5 into maxHeap (empty). Insert 15 into minHeap (15 > 5). Insert 1 into maxHeap (1 <= 5). Insert 3 into maxHeap (3 <= 5). Now maxHeap has 3 elements, minHeap has 1.

2. Step 2: Balance heaps sizes

   maxHeap size (3) > minHeap size (1) + 1, so move maxHeap.extract() (which is 5) to minHeap. Now maxHeap has [3,1], minHeap has [5,15]. Median is average of maxHeap.peek()=3 and minHeap.peek()=5, so (3+5)/2 = 4.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   Median after balancing = 4 [OK]

Hint: Balance heaps sizes, median is middle or average [OK]

Common Mistakes:

• Not balancing heaps after insertion
• Taking median as maxHeap.peek() only
• Incorrect heap extraction order

4. The following code snippet is intended to maintain the median using two heaps, but it has a bug:

function addNum(num) {
  if (num < maxHeap.peek()) {
    maxHeap.insert(num);
  } else {
    minHeap.insert(num);
  }

  if (maxHeap.size() > minHeap.size() + 1) {
    minHeap.insert(maxHeap.extract());
  } else if (minHeap.size() > maxHeap.size()) {
    maxHeap.insert(minHeap.extract());
  }
}

What is the bug in this code?

medium

A. It inserts all numbers into minHeap

B. It uses > instead of >= in the size comparison

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

D. It does not handle the case when maxHeap is empty before peek()

Solution

1. Step 1: Identify peek() usage problem

   The code calls maxHeap.peek() without checking if maxHeap is empty, causing an error on first insertion.

2. Step 2: Explain impact of missing empty check

   Without checking, calling peek() on empty maxHeap throws an error, so the first number cannot be inserted properly.

3. Final Answer:

   It does not handle the case when maxHeap is empty before peek() -> Option D

4. Quick Check:

   Empty maxHeap peek() causes error [OK]

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

Common Mistakes:

• Ignoring empty heap before peek()
• Assuming heaps always balanced before insert
• Incorrect size comparison operators

5. You are given a stream of numbers: [2, 4, 7, 1, 5, 3]. Using two heaps (max-heap for lower half, min-heap for upper half), what is the median after inserting all numbers? Also, explain why balancing the heaps is important in this process.

hard

A. 3.5; Balancing keeps heaps sizes equal or off by one to find median correctly

B. 4; Balancing is not necessary if we always insert correctly

C. 3; Balancing helps to sort the entire stream

D. 5; Balancing is used to find max value quickly

Solution

1. Step 1: Insert numbers and balance heaps

   Insert 2 (maxHeap empty, goes to maxHeap). Insert 4 (4 > 2, minHeap). Insert 7 (7 > 2, minHeap). Now minHeap has 2 elements, maxHeap 1, so move minHeap.extract() (4) to maxHeap. Insert 1 (1 <= 4, maxHeap). Insert 5 (5 > 4, minHeap). Insert 3 (3 <= 4, maxHeap). Heaps are balanced with maxHeap size 4 and minHeap size 2, move maxHeap.extract() (4) to minHeap to balance sizes.

2. Step 2: Calculate median and explain balancing

   Now maxHeap has [3,2,1] with peek()=3, minHeap has [4,5,7] with peek()=4. Since sizes equal (3 and 3), median is (3 + 4)/2 = 3.5. Balancing keeps heaps sizes equal or off by one to find median correctly from the tops.

3. Final Answer:

   3.5; Balancing keeps heaps sizes equal or off by one to find median correctly -> Option A

4. Quick Check:

   Balanced heaps give median 3.5 [OK]

Hint: Balance heaps sizes to get median from tops [OK]

Common Mistakes:

• Not balancing heaps after each insertion
• Calculating median from unsorted data
• Confusing median with max or min values