Design a structure that receives numbers one at a time. At any moment, it must return the median of all numbers seen so far.
DSA Animator › DSA Revision › Heap / Priority Queue › Find Median from Data Stream
Remember: a max heap for the lower half, and a min heap for the upper half. Their tops meet in the middle. The video solves Find Median from Data Stream (LeetCode 295, Hard) with the Two Heaps pattern from the Heap / Priority Queue topic, and you can replay every step in the interactive Find Median from Data Stream animation.
Design a structure that receives numbers one at a time. At any moment, it must return the median of all numbers seen so far.
Add 5, and the median is 5. Add 15, and it is 10, then add 1, and it is 5, then add 3, and it is 4.
Keeping a sorted list makes each insertion O of n. Sorting again for every query is even slower. Two heaps give O of log n insertion and O of 1 median.
Split the numbers into a lower half and an upper half. The lower half lives in a max heap, so its largest value is on top. The upper half lives in a min heap, so its smallest value is on top. Keep the sizes balanced, with the lower half allowed one extra number. Then the median is the top of the lower heap, or the average of both tops.
Add 5: it goes to the lower heap, and the median is 5. Add 15: it passes through the lower heap and lands in the upper heap. Now both heaps have one number, so the median is 5 plus 15 over 2, which is 10. Add 1: the lower heap holds 5 and 1, and the median is its top, 5. Add 3: 5 moves up to the upper heap, so lower holds 3 and 1, and upper holds 5 and 15. The sizes are equal, so the median is 3 plus 5 over 2, which is 4.
In code, add num to the lower max heap, then move the lower top into the upper min heap. If the upper heap becomes bigger, move its top back to the lower heap. For the median, return the lower top if it has more numbers, otherwise the average of both tops. Adding is O of log n, and finding the median is O of 1.
Remember: a max heap for the lower half, and a min heap for the upper half. Their tops meet in the middle.