C++ two heaps solution


  • 4
    L
    class MedianFinder {
    private:
        priority_queue<int, vector<int>, greater<int>> min_heap;
        priority_queue<int, vector<int>, less<int>> max_heap;
    public:
    
        // Adds a number into the data structure.
        void addNum(int num) {
            if (min_heap.empty() || (num >= min_heap.top())) {
                min_heap.emplace(num);
            } else {
                max_heap.emplace(num);
            }
            
            if (min_heap.size() > max_heap.size() + 1) {
                max_heap.emplace(min_heap.top());
                min_heap.pop();
            } else if (max_heap.size() > min_heap.size()) {
                min_heap.emplace(max_heap.top());
                max_heap.pop();
            }
        }
    
        // Returns the median of current data stream
        double findMedian() {
            return min_heap.size() == max_heap.size() 
            ? 0.5 * (min_heap.top() + max_heap.top())
            :  min_heap.top();
        }
    };

  • 0
    H

    Would be great if you could provide a worded explanation of what this does. Say, maintains the invariant that there are the same number of elements in the min_heap as there are in the max_heap. (With the caveat that the min_heap is allowed at most one number more.)


  • 0
    L

    There are two conditions.
    1): If the total number is even, then get the top of min_heap and max_heap to get the median. 2): If the total number is odd, always keep the median on min_heap. You can also keep it on the max_heap. It's your own decision.


  • 0
    Z

    just a question, how to limit the size of the heap?
    Since if we have a huge stream, it will become more and more slow when adding a new number.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.