rt,想封装一个堆,交上去发现 #3 ~ #10 都错了
#include<bits/stdc++.h>
using namespace std;
template<typename T,int N> struct Heap {
T h[N];
int tot = 0;
int size() {
return tot;
}
void push(T x) {
h[++ tot] = x;
int now = tot;
while(now >> 1) {
int nxt = now >> 1;
if(h[now] < h[nxt]) {
swap(h[now],h[nxt]);
now = nxt;
}
else {
break;
}
}
}
void pop() {
swap(h[1],h[tot]);
tot --;
int now = 1;
while((now << 1) <= tot) {
int lson = now << 1,rson = now << 1 | 1,nxt;
if(rson <= tot && h[lson] < h[rson]) {
nxt = rson;
}
else {
nxt = lson;
}
if(h[nxt] < h[now]) {
swap(h[nxt],h[now]);
now = nxt;
}
else {
break;
}
}
}
T top() {
return h[1];
}
};
Heap<int,int(1e6 + 5)> h;
int main() {
int q;
scanf("%d",&q);
while(q --) {
int op,x;
scanf("%d",&op);
if(op == 1) {
scanf("%d",&x);
h.push(x);
}
else if(op == 2) {
printf("%d\n",h.top());
}
else {
h.pop();
}
}
}