Using two heaps (both big heap and small heap)


  • 1
    S
    // using two heaps (a big heap and a small heap)
    class MedianFinder {
    private:
    priority_queue<int, vector<int>, less<int> > maxHeap; // big heap, small half
    priority_queue<int, vector<int>, greater<int> > minHeap; // small heap, big half
    
    public:
    
    // Adds a number into the data structure.
    void addNum(int num) {
        maxHeap.push(num);
        int t = maxHeap.top(); maxHeap.pop();
        minHeap.push(t);
        
        // for the length balance
        if (minHeap.size() > maxHeap.size()) {
            t = minHeap.top(); minHeap.pop();
            maxHeap.push(t);
        }
    }
    
    // Returns the median of current data stream
    double findMedian() {
        int l1 = maxHeap.size(), l2 = minHeap.size();
        if (l1 == 0 && l2 == 0) return 0.0;
        if (l1 == l2) return ( maxHeap.top() + minHeap.top() ) / 2.0;
        return l1 > l2 ? maxHeap.top() : minHeap.top();
    }
    

    };


Log in to reply
 

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