牛客网第k小（详解）c++

题目链接：第 k 小

1.题目解析

结合示例1，5是数组的个数是5，4是有4个操作，3是要查询第3小，数组刚开始有1 2 3 4 5 这5个元素，接下来都是操作，2是输出第k(3)小，输出3，1 1，向数组插入1，1 1 2 3 4 5，1 3，向数组插入3，1 1 2 3 3 4 5，2查询第3(k)小，此时第三小是2，输出2.

2.算法原理

解法：用堆维护数组流中的第k小

我们这道题虽然刚开始给了我们一堆数，又插入了一些元素，其实我们也可以把整个数组看成是一个一个来的数，比如刚开始的数组是 1 2 3 4 5 ，插入了一个1和3，1 2 3 4 5 1 3 ，就是这个数据是一个一个过来的

分两步走解决这个问题：1.创建一个大根堆(快速找到没有必要存的数) 2.维护大根堆的大小为k即可，此时堆顶元素就是第k小

如果当前有12 23 34 45 这4个数，要求第3小的数，关于第四个位置45 这个元素，它有必要存下来吗，没有必要，不管你接下来来了个0元素还是100元素，它永远都不可能成为第k小，原因就是前面有位置1 2 3 顶着呢，45到来的时候，它在4这个位置必定不可能成为第3小，所以我们可以把第四个这个45删掉，当我们发现此时已经有了3个较小元素了，这时候来了个比这三个较小的数还要大点的元素，你绝对不可能是第k小，那就可以把你给删掉，此时如何找到这堆数里面较大的数，正好就用大根堆，所以为什么大根堆能解决这个问题，因为我们发现在数据流到来的过程中，较大的数什么没有存的必要的，如何找到较大的，没有必要存的数，就使用大根堆来快速找到，当我们把这个大根堆的大小维持在K的时候，此时大根堆里面待查的元素只有k个，堆顶元素就是第k小

简单点就是大根堆，小的数都在最底下，如果这道题改成第k大的数，创建一个小根堆就可以了，后面的过程是一样的，小根堆，大的数都在最底下

代码：

#include <iostream>
#include <queue>
using namespace std;

int n, m, k;
priority_queue<int> heap; //默认是大根堆

int main()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= n; ++i)
    {
        int x; cin >> x;
        heap.push(x);
        if (heap.size() > k) heap.pop(); //把大根堆大小控制在k之内
    }
    while (m--)
    {
        int op; cin >> op;
        if (op == 1)
        {
            int x; cin >> x;
            heap.push(x);
            if (heap.size() > k) heap.pop();
        }
        else
        {
            if (heap.size() == k) cout << heap.top() << endl;
            else cout << "-1" << endl;
        }
    }
    return 0;
}