Heap and Two-Heap Median

Opening scenario

Find Median from Data Stream (LC 295): design a structure with addNum(x) and findMedian(). Numbers arrive one at a time (a stream). After each insertion you must be able to return the median of all numbers seen so far in O(1). Follow-up you should expect: Task Scheduler (LC 621) — given task labels and a nonnegative integer cooldown n, return the minimum number of CPU intervals. Each task takes one interval. Equal labels need at least n intervening intervals, occupied by other tasks or idle time. Tasks may be reordered.

LC numbers identify LeetCode problems.

For an odd number of values, the median is the middle sorted value. For an even number, it is the average of the two middle values. Query only after at least one insertion. Which parts of the sorted order must remain available to answer that query?

Question progression

Q1 — The median is "the middle of a sorted order". Why is keeping the data sorted the wrong instinct?

Question: The median needs the middle…