Median of Data Stream Using Two Heaps in DSA Go - 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 can be quickly found from the top elements of the 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 is either the top of one heap or the average of the tops of both 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 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 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 uses the top elements of the heaps.

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

A Min-heap

B Max-heap

C Both heaps store the same numbers

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 two more elements than the min-heap after insertion?

A Do nothing

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

C Remove the top from max-heap and add it to min-heap

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 does the median come from?

A Top of min-heap

B Top of max-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 of data stream?

A Uses less memory than arrays

B Only works for sorted data

C No need to balance heaps

D Fast insertion and fast median retrieval

Two heaps allow O(log n) insertion and O(1) median retrieval.

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

A Sort the entire data stream

B Insert into one heap

C Balance the heaps

D Compare with max-heap top

Sorting the entire data stream is not needed; heaps keep order efficiently.

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

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

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

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