#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
void heapify(vector<int> &v, int t) {
int s = v.size();
if ( ((s> 2*t+1 ) && (v[t] > v[2*t+1])) || ((s>2*t+2) && (v[t] > v[2*t+2]))) {
if (s>2*t+2) {
int index = v[2*t+1] > v[2*t+2] ? 2*t+2 : 2*t+1;
int temp = v[index];
v[index] = v[t];
v[t] = temp;
heapify(v, index);
} else {
int temp = v[2*t+1];
v[2*t+1] = v[t];
v[t] = temp;
heapify(v, 2*t+1);
}
}
}
void insert_h(vector<int> &v, int t) {
if (v.size() > 0) {
v.push_back(t);
t= v.size() -1;
while((t-1)/2>= 0 && v[t] < v[((t-1)/2)]) {
int temp = v[t];
v[t] = v[(t-1)/2];
v[(t-1)/2] = temp;
t = (t-1)/2;
}
} else {
v.push_back(t);
}
}
void delete_h (vector<int> &v , int t) {
for (int i = 0; i< v.size(); i++) {
if (v[i] == t) {
v[i] = v.back();
v.pop_back();
heapify(v, i);
break;
}
}
}
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
vector<int> v;
int n;
int q;
int t;
cin>>n;
for (int i =0; i<n; i++) {
cin>>q;
if (q == 1) {
cin>>t;
insert_h(v,t);
} else if (q == 2) {
cin>>t;
delete_h(v,t);
} else {
cout<<v[0]<<endl;
}
}
return 0;
No comments:
Post a Comment