已知 pop() 有一定问题,求调。
struct heap {
int a[N], t = 0;
int size() {
return t;
}
int empty() {
return !size();
}
int push(int k) {
a[++t] = k;
int c = t;
while(a[c] > a[c / 2] && c > 1) {
swap(a[c], a[c / 2]);
c /= 2;
}
return c;
}
int top() {
assert(size());
return a[1];
}
void pop() {
assert(size());
swap(a[1], a[t--]);
int c = 1;
while(a[c] < max(a[c * 2], a[c * 2 + 1]) && c * 2 <= t) {
if(a[c * 2] > a[c * 2] + 1 || c * 2 == t) {
swap(a[c], a[c * 2]);
c *= 2;
} else {
swap(a[c], a[c * 2 + 1]);
c *= 2, c += 1;
}
}
}
};