Two Heaps

// Two Heaps: Find Median from Data Stream
class MedianFinder {
    // max-heap for the lower half
    PriorityQueue<Integer> lo = new PriorityQueue<>(Collections.reverseOrder());
    // min-heap for the upper half
    PriorityQueue<Integer> hi = new PriorityQueue<>();

    void addNum(int num) {
        lo.offer(num);                   // always add to max-heap first
        hi.offer(lo.poll());              // move max of lower to upper

        if (lo.size() < hi.size()) {     // keep lo.size ≥ hi.size
            lo.offer(hi.poll());
        }
    }

    double findMedian() {
        if (lo.size() > hi.size()) {
            return lo.peek();              // odd count: median is max-heap top
        }
        return (lo.peek() + hi.peek()) / 2.0; // even: average of both tops
    }
}

// Two Heaps: Find Median from Data Stream
import "container/heap"

// MaxHeap implements heap.Interface for the lower half
type MaxHeap []int

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

// MinHeap implements heap.Interface for the upper half
type MinHeap []int

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

type MedianFinder struct {
    lo *MaxHeap // max-heap for the lower half
    hi *MinHeap // min-heap for the upper half
}

func Constructor() MedianFinder {
    lo := &MaxHeap{}; hi := &MinHeap{}
    heap.Init(lo); heap.Init(hi)
    return MedianFinder{lo, hi}
}

func (mf *MedianFinder) AddNum(num int) {
    heap.Push(mf.lo, num)                      // always add to max-heap first
    heap.Push(mf.hi, heap.Pop(mf.lo))          // move max of lower to upper
    if mf.lo.Len() < mf.hi.Len() {            // keep lo.size ≥ hi.size
        heap.Push(mf.lo, heap.Pop(mf.hi))
    }
}

func (mf *MedianFinder) FindMedian() float64 {
    if mf.lo.Len() > mf.hi.Len() {
        return float64((*mf.lo)[0])           // odd count: max-heap top
    }
    return float64((*mf.lo)[0]+(*mf.hi)[0]) / 2.0 // even: average
}

# Two Heaps: Find Median from Data Stream
import heapq

class MedianFinder:
    def __init__(self):
        self.lo: list[int] = []   # max-heap (negate values)
        self.hi: list[int] = []   # min-heap

    def add_num(self, num: int) -> None:
        heapq.heappush(self.lo, -num)            # add to max-heap
        heapq.heappush(self.hi, -heapq.heappop(self.lo))  # move max to upper

        if len(self.lo) < len(self.hi):  # keep lo.size ≥ hi.size
            heapq.heappush(self.lo, -heapq.heappop(self.hi))

    def find_median(self) -> float:
        if len(self.lo) > len(self.hi):
            return -self.lo[0]             # odd count: max-heap top
        return (-self.lo[0] + self.hi[0]) / 2  # even: average

// Two Heaps: Find Median from Data Stream
use std::collections::BinaryHeap;
use std::cmp::Reverse;

struct MedianFinder {
    lo: BinaryHeap<i32>,          // max-heap for the lower half
    hi: BinaryHeap<Reverse<i32>>,  // min-heap for the upper half
}

impl MedianFinder {
    pub fn new() -> Self {
        MedianFinder {
            lo: BinaryHeap::new(),
            hi: BinaryHeap::new(),
        }
    }

    pub fn add_num(&mut self, num: i32) {
        self.lo.push(num);                          // always add to max-heap first
        let top = self.lo.pop().unwrap();
        self.hi.push(Reverse(top));                 // move max of lower to upper
        if self.lo.len() < self.hi.len() {          // keep lo.size ≥ hi.size
            let Reverse(v) = self.hi.pop().unwrap();
            self.lo.push(v);
        }
    }

    pub fn find_median(&self) -> f64 {
        if self.lo.len() > self.hi.len() {
            return *self.lo.peek().unwrap() as f64; // odd: max-heap top
        }
        let lo_top = *self.lo.peek().unwrap() as f64;
        let Reverse(hi_top) = *self.hi.peek().unwrap();
        (lo_top + hi_top as f64) / 2.0             // even: average of both tops
    }
}

// Two Heaps: Find Median from Data Stream
class MedianFinder {
    // max-heap for the lower half (negate values to simulate max-heap)
    private lo: MinPriorityQueue<number> = new MinPriorityQueue();
    // min-heap for the upper half
    private hi: MinPriorityQueue<number> = new MinPriorityQueue();

    addNum(num: number): void {
        this.lo.enqueue(-num);              // negate for max-heap behavior
        this.hi.enqueue(-this.lo.dequeue()!); // move max of lower to upper

        if (this.lo.size() < this.hi.size()) { // keep lo.size ≥ hi.size
            this.lo.enqueue(-this.hi.dequeue()!);
        }
    }

    findMedian(): number {
        if (this.lo.size() > this.hi.size()) {
            return -this.lo.front()!;       // odd count: median is max-heap top
        }
        return (-this.lo.front()! + this.hi.front()!) / 2; // even: average
    }
}

// Ensure heaps are balanced after any add/remove
void rebalance() {
    if (lo.size() > hi.size() + 1) {
        hi.offer(lo.poll());     // move max of lower to upper
    } else if (hi.size() > lo.size()) {
        lo.offer(hi.poll());     // move min of upper to lower
    }
}

// Ensure heaps are balanced after any add/remove
func (mf *MedianFinder) rebalance() {
    if mf.lo.Len() > mf.hi.Len()+1 {
        heap.Push(mf.hi, heap.Pop(mf.lo)) // move max of lower to upper
    } else if mf.hi.Len() > mf.lo.Len() {
        heap.Push(mf.lo, heap.Pop(mf.hi)) // move min of upper to lower
    }
}

# Ensure heaps are balanced after any add/remove
def rebalance(self) -> None:
    if len(self.lo) > len(self.hi) + 1:
        heapq.heappush(self.hi, -heapq.heappop(self.lo))  # move max to upper
    elif len(self.hi) > len(self.lo):
        heapq.heappush(self.lo, -heapq.heappop(self.hi))  # move min to lower

// Ensure heaps are balanced after any add/remove
fn rebalance(&mut self) {
    if self.lo.len() > self.hi.len() + 1 {
        let top = self.lo.pop().unwrap();
        self.hi.push(Reverse(top));  // move max of lower to upper
    } else if self.hi.len() > self.lo.len() {
        let Reverse(v) = self.hi.pop().unwrap();
        self.lo.push(v);             // move min of upper to lower
    }
}

// Ensure heaps are balanced after any add/remove
rebalance(): void {
    if (this.lo.size() > this.hi.size() + 1) {
        this.hi.enqueue(-this.lo.dequeue()!); // move max of lower to upper
    } else if (this.hi.size() > this.lo.size()) {
        this.lo.enqueue(-this.hi.dequeue()!); // move min of upper to lower
    }
}