leetcode c++做题思路和题解（5）——堆的例题和总结

堆和优先队列

堆的简介, 是一种二叉树, 有最大堆和最小堆miniheap. 通常用于构建优先队列.

0. 目录

1. 数据流中的第K大元素

1. 数据流中的第K大元素

数据流中的第K大元素

复杂度为log2(N)

class KthLargest {
private:
    priority_queue<int, vector<int>, greater<int> > buf;//最小堆
    int mk;
public:
    KthLargest(int k, vector<int>& nums):mk(k) { 
        if(nums.size() <= k) {
            for(int a:nums) buf.push(a);
            if(nums.size() == k-1) buf.push(INT_MIN);//确保元素满足k个,INT_MIN是int类型的最小值
            return;
        } 
        int i=0;
        for(;i<k;++i)
            buf.push(nums[i]);
        for(;i<nums.size();++i)
            add(nums[i]);
    }
    
    int add(int val) {
        if(val<=buf.top()) return buf.top();
        buf.pop();
        buf.push(val);
        return buf.top();
    }
};

/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest* obj = new KthLargest(k, nums);
 * int param_1 = obj->add(val);
 */