题目
堆（优先队列）
思路
这道题是求一个数据流中的第 k k k 小数，我们可以维护一个大根堆，堆的容量为 k k k，这样，堆顶元素就始终是数据流中的第 k k k 小数。
具体来说，应该先建立一个容量为 k k k 的数组，维护数组中元素个数以及数组长度，然后进行出堆入堆操作，具体见代码。
代码
#include <iostream>
using namespace std;
class Heap {
// 存放堆元素的数组，堆的大小，堆中元素个数
int *data, n, size;
// 元素加入堆
void push(int val) {
data[size++] = val;
int i = size - 1;
while (i > 0 && data[i] > data[(i - 1) >> 1]) {
swap(data[i], data[(i - 1) >> 1]);
i = (i - 1) >> 1;
}
}
// 弹出堆顶元素
int pop() {
int res = data[0];
data[0] = data[--size];
int i = 0, j = 0;
while (2 * i + 1 < size) {
j = 2 * i + 1;
if (j + 1 < size && data[j + 1] > data[j]) {
j++;
}
if (data[i] < data[j]) {
swap(data[i], data[j]);
i = j;
} else {
break;
}
}
return res;
}
public:
Heap(int n) : n(n), size(0) { data = new int[n]; }
~Heap() { delete[] data; }
void add(int val) {
if (size < n) {
// 必须加入
push(val);
} else {
if (val < data[0]) {
// 否则只有当要加入的值小于堆顶元素时才能加入
// 先弹出堆顶元素
pop();
// 再加入元素
push(val);
}
}
}
int top() {
if (size == 0 || size < n) return -1;
return data[0];
}
};
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n = 0, m = 0, k = 0;
cin >> n >> m >> k;
// 建立堆
Heap heap(k);
int a = 0, b = 0;
for (int i = 0; i < n; i++) {
cin >> a;
heap.add(a);
}
while (m--) {
cin >> a;
if (a == 1) {
cin >> b;
// 加入堆中
heap.add(b);
} else {
// 输出第k小数
cout << heap.top() << endl;
}
}
return 0;
}