Two Heaps: the Running Median

// The lower half in a max-heap, the upper half in a min-heap; the lower half may hold one more.
class MedianFinder {
    priority_queue<int> low;                                   // its top is the largest of the lower half
    priority_queue<int, vector<int>, greater<int>> high;      // its top is the smallest of the upper half
public:
    void addNum(int num) {
        low.push(num);
        high.push(low.top());                                  // the largest of the lower half moves up
        low.pop();
        if (high.size() > low.size()) {                        // keep the lower half the bigger one
            low.push(high.top());
            high.pop();
        }
    }
    double findMedian() {
        if (low.size() > high.size()) return low.top();
        return ((double)low.top() + high.top()) / 2;           // a double before adding: two ints can overflow
    }
};

import heapq


class MedianFinder:
    """The lower half in a max-heap (as negatives), the upper half in a min-heap; the lower half may hold one more."""

    def __init__(self):
        self.low, self.high = [], []

    def addNum(self, num):
        heapq.heappush(self.high, -heapq.heappushpop(self.low, -num))   # the largest of the lower half moves up
        if len(self.high) > len(self.low):
            heapq.heappush(self.low, -heapq.heappop(self.high))        # keep the lower half the bigger one

    def findMedian(self):
        if len(self.low) > len(self.high):
            return -self.low[0]
        return (-self.low[0] + self.high[0]) / 2

// The lower half in a max-heap, the upper half in a min-heap; the lower half may hold one more.
static class MedianFinder {
    PriorityQueue<Integer> low = new PriorityQueue<>(Collections.reverseOrder());   // top: the lower half's largest
    PriorityQueue<Integer> high = new PriorityQueue<>();                            // top: the upper half's smallest

    void addNum(int num) {
        low.offer(num);
        high.offer(low.poll());                                 // the largest of the lower half moves up
        if (high.size() > low.size()) low.offer(high.poll());   // keep the lower half the bigger one
    }

    double findMedian() {
        if (low.size() > high.size()) return low.peek();
        return ((double) low.peek() + high.peek()) / 2;         // a double before adding: two ints can overflow
    }
}

// The lower half in a max-heap, the upper half in a min-heap: Introduction to Heaps' MinHeap, twice.
class MedianFinder {
    constructor() {
        this.low = new MinHeap((x, y) => x > y);   // the largest of the lower half on top
        this.high = new MinHeap();                 // the smallest of the upper half on top
    }
    addNum(num) {
        this.low.push(num);
        this.high.push(this.low.pop());            // the largest of the lower half moves up
        if (this.high.a.length > this.low.a.length) this.low.push(this.high.pop());   // the lower half the bigger one
    }
    findMedian() {
        if (this.low.a.length > this.high.a.length) return this.low.a[0];
        return (this.low.a[0] + this.high.a[0]) / 2;
    }
}

The running median of [5, 15, 1, 3, 8, 7, 2] — Every value so far, in order: the low half, then the high half, each half's top marked. Green is the median; indigo, the value just added.

import heapq
from collections import Counter


class DualHeap:
    """A running median that can delete: a deleted value stays in its heap until it reaches the top."""

    def __init__(self):
        self.low, self.high = [], []          # the lower half as negatives (a max-heap), the upper half
        self.gone = Counter()                 # deleted, but maybe still inside a heap
        self.n_low = self.n_high = 0          # live values in each half

    def _clean(self, heap, sign):             # drop deleted values sitting on top
        while heap and self.gone[sign * heap[0]]:
            self.gone[sign * heapq.heappop(heap)] -= 1

    def _balance(self):                       # the lower half holds the extra value, if any
        if self.n_low > self.n_high + 1:
            heapq.heappush(self.high, -heapq.heappop(self.low))
            self.n_low, self.n_high = self.n_low - 1, self.n_high + 1
            self._clean(self.low, -1)
        elif self.n_high > self.n_low:
            heapq.heappush(self.low, -heapq.heappop(self.high))
            self.n_low, self.n_high = self.n_low + 1, self.n_high - 1
            self._clean(self.high, 1)

    def add(self, x):
        if not self.low or x <= -self.low[0]:
            heapq.heappush(self.low, -x)
            self.n_low += 1
        else:
            heapq.heappush(self.high, x)
            self.n_high += 1
        self._balance()

    def remove(self, x):
        self.gone[x] += 1                     # mark it; it leaves the heap when it surfaces
        if x <= -self.low[0]:
            self.n_low -= 1
            if x == -self.low[0]:
                self._clean(self.low, -1)
        else:
            self.n_high -= 1
            if x == self.high[0]:
                self._clean(self.high, 1)
        self._balance()

    def median(self):
        if self.n_low > self.n_high:
            return float(-self.low[0])
        return (-self.low[0] + self.high[0]) / 2


def median_sliding_window(nums, k):
    window = DualHeap()
    for x in nums[:k]:
        window.add(x)
    out = [window.median()]
    for i in range(k, len(nums)):
        window.add(nums[i])
        window.remove(nums[i - k])
        out.append(window.median())
    return out

static class MedianFinder {
    PriorityQueue<Integer> low = new PriorityQueue<>(Collections.reverseOrder());
    PriorityQueue<Integer> high = new PriorityQueue<>();

    void addNum(int num) {
        low.offer(num);
        high.offer(low.poll());
        if (high.size() > low.size()) low.offer(high.poll());
    }

    double findMedian() {
        if (low.size() > high.size()) return low.peek();
        return (low.peek() + high.peek()) / 2;            // int + int, then int / int
    }
}

double findMedian() {
    if (low.size() > high.size()) return low.peek();
    return (low.peek() + high.peek()) / 2.0;          // the int sum overflows first
}

import heapq


class MedianFinder:
    def __init__(self):
        self.low, self.high = [], []

    def addNum(self, num):
        if len(self.low) <= len(self.high):
            heapq.heappush(self.low, -num)        # the smaller half, whatever the value
        else:
            heapq.heappush(self.high, num)

    def findMedian(self):
        if len(self.low) > len(self.high):
            return -self.low[0]
        return (-self.low[0] + self.high[0]) / 2