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.