Median of Data Stream Using Two Heaps in DSA C++ - 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 tops of the heaps.

beginner

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

Balancing ensures that the heaps represent equal halves of the data or differ by one element, which helps in correctly calculating the median.

beginner

In the two heaps method, what does the max-heap store?

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

intermediate

How do you find the median when 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 is the top element(s) of the heaps.

What data structure is used to store the larger half of the numbers in the two heaps method?

A Min-heap

B Max-heap

C Queue

D Stack

The larger half of the numbers is stored in a min-heap so that the smallest number in the larger half is easily accessible.

If the max-heap has 5 elements and the min-heap has 3 elements, what should you do?

A Move the top element from min-heap to max-heap

B Move the top element from max-heap to min-heap

C Add a new element to min-heap

D Do nothing

The heaps should be balanced or differ by at most one element. Moving the top element from max-heap to min-heap balances the sizes.

What is the median when both heaps have the same number of elements?

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

When heaps are equal in size, the median is the average of the two middle values, which are the tops of the two heaps.

Why is a max-heap used for the smaller half instead of a min-heap?

A To store negative numbers

B To sort numbers in ascending order

C Because min-heap is slower

D To quickly access the largest number in the smaller half

A max-heap allows quick access to the largest number in the smaller half, which helps in balancing and median calculation.

What is the first step when adding a new number to the data stream using two heaps?

A Add to max-heap always

B Add to min-heap always

C Add to max-heap if number is smaller than or equal to max-heap top

D Add to min-heap if number is smaller than max-heap top

The new number is compared with the max-heap top to decide which heap it belongs to, ensuring correct partitioning.

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

Think about dividing numbers into two parts and how to find middle values quickly.

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.