Find Median from a Data Stream

class MedianFinder {
    priority_queue<int> lo;                            // max-heap
    priority_queue<int, vector<int>, greater<int>> hi; // min-heap
public:
    void addNum(int n) {
        lo.push(n);
        hi.push(lo.top()); lo.pop();
        if (hi.size() > lo.size()) { lo.push(hi.top()); hi.pop(); }
    }
    double findMedian() {
        return lo.size() > hi.size() ? lo.top() : (lo.top() + hi.top()) / 2.0;
    }
};

import "container/heap"

type intMaxHeap []int

func (h intMaxHeap) Len() int            { return len(h) }
func (h intMaxHeap) Less(i, j int) bool  { return h[i] > h[j] }
func (h intMaxHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *intMaxHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *intMaxHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

type intMinHeap []int

func (h intMinHeap) Len() int            { return len(h) }
func (h intMinHeap) Less(i, j int) bool  { return h[i] < h[j] }
func (h intMinHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *intMinHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *intMinHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

type MedianFinder struct {
    lo *intMaxHeap
    hi *intMinHeap
}

func Constructor() MedianFinder {
    return MedianFinder{lo: &intMaxHeap{}, hi: &intMinHeap{}}
}

func (m *MedianFinder) AddNum(num int) {
    heap.Push(m.lo, num)
    heap.Push(m.hi, heap.Pop(m.lo))
    if m.hi.Len() > m.lo.Len() {
        heap.Push(m.lo, heap.Pop(m.hi))
    }
}

func (m *MedianFinder) FindMedian() float64 {
    if m.lo.Len() > m.hi.Len() {
        return float64((*m.lo)[0])
    }
    return (float64((*m.lo)[0]) + float64((*m.hi)[0])) / 2.0
}

import heapq

class MedianFinder:
    def __init__(self):
        self.lo = []  # max-heap (store negatives)
        self.hi = []  # min-heap

    def addNum(self, num: int) -> None:
        heapq.heappush(self.lo, -num)
        heapq.heappush(self.hi, -heapq.heappop(self.lo))
        if len(self.hi) > len(self.lo):
            heapq.heappush(self.lo, -heapq.heappop(self.hi))

    def findMedian(self) -> float:
        if len(self.lo) > len(self.hi):
            return float(-self.lo[0])
        return (-self.lo[0] + self.hi[0]) / 2.0

class Heap {
    constructor(cmp) { this.h = []; this.cmp = cmp; }
    size() { return this.h.length; }
    top() { return this.h[0]; }
    push(x) {
        this.h.push(x);
        let i = this.h.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.cmp(this.h[i], this.h[p]) < 0) {
                [this.h[i], this.h[p]] = [this.h[p], this.h[i]];
                i = p;
            } else break;
        }
    }
    pop() {
        const top = this.h[0];
        const last = this.h.pop();
        if (this.h.length > 0) {
            this.h[0] = last;
            let i = 0;
            const n = this.h.length;
            while (true) {
                const l = i * 2 + 1, r = i * 2 + 2;
                let best = i;
                if (l < n && this.cmp(this.h[l], this.h[best]) < 0) best = l;
                if (r < n && this.cmp(this.h[r], this.h[best]) < 0) best = r;
                if (best === i) break;
                [this.h[i], this.h[best]] = [this.h[best], this.h[i]];
                i = best;
            }
        }
        return top;
    }
}

class MedianFinder {
    constructor() {
        this.lo = new Heap((a, b) => b - a); // max-heap
        this.hi = new Heap((a, b) => a - b); // min-heap
    }
    addNum(num) {
        this.lo.push(num);
        this.hi.push(this.lo.pop());
        if (this.hi.size() > this.lo.size()) {
            this.lo.push(this.hi.pop());
        }
    }
    findMedian() {
        if (this.lo.size() > this.hi.size()) return this.lo.top();
        return (this.lo.top() + this.hi.top()) / 2.0;
    }
}

class MedianFinder {
    private PriorityQueue<Integer> lo; // max-heap
    private PriorityQueue<Integer> hi; // min-heap

    public MedianFinder() {
        lo = new PriorityQueue<>(Comparator.reverseOrder());
        hi = new PriorityQueue<>();
    }

    public void addNum(int num) {
        lo.offer(num);
        hi.offer(lo.poll());
        if (hi.size() > lo.size()) {
            lo.offer(hi.poll());
        }
    }

    public double findMedian() {
        if (lo.size() > hi.size()) return lo.peek();
        return (lo.peek() + hi.peek()) / 2.0;
    }
}

class Heap<T> {
    private h: T[] = [];
    constructor(private cmp: (a: T, b: T) => number) {}
    size(): number { return this.h.length; }
    top(): T { return this.h[0]; }
    push(x: T): void {
        this.h.push(x);
        let i = this.h.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.cmp(this.h[i], this.h[p]) < 0) {
                [this.h[i], this.h[p]] = [this.h[p], this.h[i]];
                i = p;
            } else break;
        }
    }
    pop(): T {
        const top = this.h[0];
        const last = this.h.pop()!;
        if (this.h.length > 0) {
            this.h[0] = last;
            let i = 0;
            const n = this.h.length;
            while (true) {
                const l = i * 2 + 1, r = i * 2 + 2;
                let best = i;
                if (l < n && this.cmp(this.h[l], this.h[best]) < 0) best = l;
                if (r < n && this.cmp(this.h[r], this.h[best]) < 0) best = r;
                if (best === i) break;
                [this.h[i], this.h[best]] = [this.h[best], this.h[i]];
                i = best;
            }
        }
        return top;
    }
}

class MedianFinder {
    private lo: Heap<number>;
    private hi: Heap<number>;

    constructor() {
        this.lo = new Heap<number>((a, b) => b - a); // max-heap
        this.hi = new Heap<number>((a, b) => a - b); // min-heap
    }

    addNum(num: number): void {
        this.lo.push(num);
        this.hi.push(this.lo.pop());
        if (this.hi.size() > this.lo.size()) {
            this.lo.push(this.hi.pop());
        }
    }

    findMedian(): number {
        if (this.lo.size() > this.hi.size()) return this.lo.top();
        return (this.lo.top() + this.hi.top()) / 2.0;
    }
}