堆和优先队列

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

0. 目录

数据流中的第K大元素

1. 数据流中的第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);

 */

巴特西

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

堆和优先队列

0. 目录

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

最新文章

热门文章