Skip to main content

Median from Data Stream

Learn Median from Data Stream (Heap, Data Structures & Algorithms) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.

Maintaining a Running Median with Two Heaps Split the numbers seen so far into two halves: a MAX-heap holding the SMALLER half (its top is the largest of the small numbers), and a MIN-heap holding the LARGER half (its top is the smallest of the large numbers). The median is derivable from the two tops in O(1) - inserting a new number costs O(log n) to keep both heaps balanced.

More lessons in Heap