DiffPush Tier Heaps · Hard Problems O(log n) add, O(1) median · O(n)
A toll plaza logs one vehicle count per hour and regulators request the running median after every reading — the hourly figure splitting all readings into equal halves. The gauge never re-sorts: it keeps the lower half of readings in a max-topped vault and the upper half in a min-topped vault, rebalancing after each insert so the medians are always one or two tops away.
Input: A list of operations: ["add", value] or ["findMedian"].
Output: Return the list of medians produced by every findMedian operation, in order.
1 <= number of operations <= 5 * 10^4-10^5 <= values <= 10^5add: O(log n); findMedian: O(1)Input: {"operations":[["add",1],["add",2],["findMedian"],["add",3],["findMedian"]]}
Output: [1.5,2]
Two readings split the median halfway; the third reading makes 2 the true middle.
Input: {"operations":[["add",5],["findMedian"],["add",15],["findMedian"],["add",1],["findMedian"]]}
Output: [5,10,5]
Each median is the middle of {5}, then {1,5,15} → 5... specifically 5, 10, 5.