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.