Find Median from Data Stream

1package pkg5leetcode.blind75;2 3/*4 * Find Median from Data Stream | LC 2955 * APPROACH: Two heaps: max-heap lower half, min-heap upper half balanced.6 * COMPLEXITY: addNum O(log n), findMedian O(1)7 */8import java.util.*;9 10public class blind75_LC295FindMedianFromDataStream {11    static class MedianFinder {12        PriorityQueue<Integer> lo = new PriorityQueue<>(Collections.reverseOrder());13        PriorityQueue<Integer> hi = new PriorityQueue<>();14 15        void addNum(int num) {16            lo.offer(num);17            hi.offer(lo.poll());18            if (lo.size() < hi.size()) lo.offer(hi.poll());19        }20 21        double findMedian() {22            if (lo.size() > hi.size()) return lo.peek();23            return (lo.peek() + hi.peek()) / 2.0;24        }25    }26 27    public static void main(String[] args) {28        MedianFinder mf = new MedianFinder();29        mf.addNum(1);30        mf.addNum(2);31        check(mf.findMedian() == 1.5, "case1");32        mf.addNum(3);33        check(mf.findMedian() == 2.0, "case2");34        System.out.println("all tests passed");35    }36 37    static void check(boolean cond, String name) {38        if (!cond) throw new AssertionError("FAILED: " + name);39        System.out.println("  PASS " + name);40    }41}