Median of a Stream of Integers

import java.util.ArrayList;
import java.util.Collections;
import java.util.PriorityQueue;

class Solution {
    public ArrayList<Double> getMedian(int[] arr) {
        // low: max-heap with the smaller half. Its top is the largest of that half.
        // high: min-heap with the larger half. Its top is the smallest of that half.
        PriorityQueue<Integer> low = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> high = new PriorityQueue<>();
        ArrayList<Double> answers = new ArrayList<>();

        for (int x : arr) {
            // 1. Put x into low, whatever its size.
            low.offer(x);
            // 2. Move low's largest across to high. This keeps every value in low <= every value in high.
            high.offer(low.poll());
            // 3. Step 2 can leave high one too big. Move its smallest back to low.
            if (high.size() > low.size()) {
                low.offer(high.poll());
            }

            // Odd count: the middle is low's top (low has one extra).
            // Even count: the two middle numbers are the two tops, so average them.
            if (low.size() > high.size()) {
                answers.add((double) low.peek());
            } else {
                answers.add((low.peek() + (double) high.peek()) / 2.0);
            }
        }
        return answers;
    }
}

import heapq
from typing import List

class Solution:
    def getMedian(self, arr: List[int]) -> List[float]:
        # low: max-heap with the smaller half (stored as negatives).
        # high: min-heap with the larger half.
        low: List[int] = []   # max-heap via negative values
        high: List[int] = []  # min-heap
        answers: List[float] = []

        for x in arr:
            # 1. Put x into low, whatever its size.
            heapq.heappush(low, -x)
            # 2. Move low's largest across to high. This keeps every value in low <= every value in high.
            val = -heapq.heappop(low)
            heapq.heappush(high, val)
            # 3. Step 2 can leave high one too big. Move its smallest back to low.
            if len(high) > len(low):
                heapq.heappush(low, -heapq.heappop(high))

            # Odd count: the middle is low's top (low has one extra).
            # Even count: the two middle numbers are the two tops, so average them.
            if len(low) > len(high):
                answers.append(float(-low[0]))
            else:
                answers.append((-low[0] + high[0]) / 2.0)

        return answers

class PriorityQueue<T> {
    private heap: T[] = [];
    constructor(private compare: (a: T, b: T) => number) {}

    push(val: T): void {
        this.heap.push(val);
        this.bubbleUp(this.heap.length - 1);
    }

    pop(): T | undefined {
        if (this.heap.length === 0) return undefined;
        const top = this.heap[0];
        const bottom = this.heap.pop()!;
        if (this.heap.length > 0) {
            this.heap[0] = bottom;
            this.bubbleDown(0);
        }
        return top;
    }

    peek(): T | undefined {
        return this.heap[0];
    }

    size(): number {
        return this.heap.length;
    }

    isEmpty(): boolean {
        return this.heap.length === 0;
    }

    private bubbleUp(idx: number): void {
        while (idx > 0) {
            const p = (idx - 1) >> 1;
            if (this.compare(this.heap[idx], this.heap[p]) < 0) {
                [this.heap[idx], this.heap[p]] = [this.heap[p], this.heap[idx]];
                idx = p;
            } else {
                break;
            }
        }
    }

    private bubbleDown(idx: number): void {
        const len = this.heap.length;
        while (true) {
            let smallest = idx;
            const left = 2 * idx + 1;
            const right = 2 * idx + 2;
            if (left < len && this.compare(this.heap[left], this.heap[smallest]) < 0) {
                smallest = left;
            }
            if (right < len && this.compare(this.heap[right], this.heap[smallest]) < 0) {
                smallest = right;
            }
            if (smallest !== idx) {
                [this.heap[idx], this.heap[smallest]] = [this.heap[smallest], this.heap[idx]];
                idx = smallest;
            } else {
                break;
            }
        }
    }
}

export function getMedian(arr: number[]): number[] {
    // low: max-heap with the smaller half. Its top is the largest of that half.
    // high: min-heap with the larger half. Its top is the smallest of that half.
    const low = new PriorityQueue<number>((a, b) => b - a);
    const high = new PriorityQueue<number>((a, b) => a - b);
    const answers: number[] = [];

    for (const x of arr) {
        // 1. Put x into low, whatever its size.
        low.push(x);
        // 2. Move low's largest across to high. This keeps every value in low <= every value in high.
        high.push(low.pop()!);
        // 3. Step 2 can leave high one too big. Move its smallest back to low.
        if (high.size() > low.size()) {
            low.push(high.pop()!);
        }

        // Odd count: the middle is low's top (low has one extra).
        // Even count: the two middle numbers are the two tops, so average them.
        if (low.size() > high.size()) {
            answers.push(low.peek()!);
        } else {
            answers.push((low.peek()! + high.peek()!) / 2.0);
        }
    }
    return answers;
}