Heap Thinking Process
Median is the middle value in an ordered integer list, so median will halve the list into a bigger half and a smaller half (When the size of list is not even, w
Median is the middle value in an ordered integer list, so median will halve the list into `a bigger half and a smaller half` (When the size of list is not even, we can put the middle value in either half).\n* If the size of the list is even, median is the mean of the two middle value, i.e., `the MEAN of the minimum of the bigger half AND the maximum of the smaller half`. \n* If the size of the list is odd, median is `the maximum of the smaller half OR the maximum of the smaller half`.\n\n**Heap** is designed for the case that we need to repeatly do minimum or  maximum calculation.\n\nSo we maintain an invariant that smaller half is in maxHeap, and bigger half is in minHeap. This requires at any time:\n* maximum of maxHeap < minimum of minHeap\n* size of maxHeap and minHeap can differ at most 1\n\n****\n```\nclass MedianFinder {\n    \n    private PriorityQueue<Integer> maxHeap; // Smaller half.\n    private PriorityQueue<Integer> minHeap; // Bigger half.\n\n    /** initialize your data structure here. */\n    public MedianFinder() {\n        maxHeap = new PriorityQueue<>((a, b) -> Integer.compare(b, a));\n        minHeap = new PriorityQueue<>();\n    }\n    \n    public void addNum(int num) {\n        // Maintains the invariant that smaller half is in maxHeap, and bigger half is in minHeap\n        if (maxHeap.isEmpty() || num <= maxHeap.peek()) { // num belongs to smaller half\n            maxHeap.offer(num);\n            if (maxHeap.size() > minHeap.size() + 1) {\n                minHeap.offer(maxHeap.poll());\n            }\n        } else { // num belongs to bigger half\n            minHeap.offer(num);\n            if (minHeap.size() > maxHeap.size() + 1) {\n                maxHeap.offer(minHeap.poll());\n            }\n        }\n    }\n    \n    public double findMedian() {\n        if (minHeap.size() > maxHeap.size()) {\n            return (double) minHeap.peek();\n        } else if (minHeap.size() < maxHeap.size()) {\n            return (double) maxHeap.peek();\n        } else {\n            return (minHeap.peek() + maxHeap.peek()) / 2.0;\n        }\n    }\n}\n```\n**(\u4EBA \u2022\u0348\u1D17\u2022\u0348)** Thanks for voting!
[]