<aside>
💡 Imagine a pyramid. The median is either top or average of highest elements from both sides. Create MaxHeap to store left side, create MinHeap to store right side.
To add: If sizes are same → add to right, move highest to left Else → add to left, move highest to right
To find median: If left is bigger → get highest of left Else → median
</aside>
https://leetcode.com/problems/find-median-from-data-stream/
function MedianFinder() {
this.left = new MaxHeap();
this.right = new MinHeap();
}
MedianFinder.prototype.addNum = function (num) {
if (this.left.heap.length === this.right.heap.length) {
this.right.add(num);
this.left.add(this.right.pop());
} else {
this.left.add(num);
this.right.add(this.left.pop());
}
};
MedianFinder.prototype.findMedian = function () {
if (this.left.heap.length > this.right.heap.length) {
return this.left.heap[0];
} else {
return (this.left.heap[0] + this.right.heap[0]) / 2;
}
};