leetcode 703. 数据流中的第K大元素 小顶堆

建立一个大小为k的最小堆，堆顶就是第k大的元素
数据流中如果有比k大的元素，入堆，重新调整，保持一共k个元素
如果比k小直接返回堆顶即可

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

#define debug(x) cout<<#x<<": "<<x<<endl;

class KthLargest {
public:
    vector<int> numss;
    int kk;
    KthLargest(int k, vector<int>& nums) {
        kk = k;
        numss = nums;
        make_heap(numss.begin(),numss.end(),greater<int>()  );
        while( numss.size()>kk ){
            pop_heap(numss.begin(),numss.end(),greater<int>()  );
            numss.pop_back();
        }
    }

    int add(int val) {
        if( numss.size() < kk ){
            numss.push_back( val );
            make_heap(numss.begin(),numss.end(),greater<int>()  );
            return numss[0];
        }else if( val <= numss[0] ){
            return numss[0];
        }else{
            numss.push_back( val );
            pop_heap(numss.begin(),numss.end(),greater<int>()  );
            numss.pop_back();
            return numss[0];
        }
        return 0;
    }
};


int main()
{
    int k = 3;
    vector<int> arr = {4,5,8,2};
    KthLargest kthLargest(k,arr);

    debug( kthLargest.add(3) ); // returns 4
    debug( kthLargest.add(5) );// returns 5
    debug( kthLargest.add(10) );// returns 5
    debug( kthLargest.add(9) );// returns 8
    debug( kthLargest.add(4) );// returns 8

    return 0;
}