AOJ

# # 解答


#define ll long long
#define loop(x, start, end) for(int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)

#define left(x) (x * 2)
#define right(x) (x * 2 + 1)
#define parent(x) (x / 2)

class PriorityQueue {
public:
PriorityQueue() {
vec.push_back(-99999);
size = 0;
}

void insert(int key) {
size++;
if (size >= vec.size()) {
vec.push_back(key);
} else {
vec[size] = key;
}

int index = size;
int p = parent(index);
while (index > 1 && vec[p] < vec[index]) {
swap(vec[p], vec[index]);
index = p;
p = parent(index);
}
}

int top() {
return vec[1];
}

void pop() {
vec[1] = vec[size];
maxHeapify(1);
size--;
}

int topAndPop() {
int _max = top();
pop();
return _max;
}

void print() {
loop(i, 1, size+1) cout << " " << vec[i];
cout << endl;
}

private:
vector<int> vec;
int size;

void maxHeapify(int index) {
int last = size;
int l = left(index);
int r = right(index);
int largest;
if (l <= last && vec[l] > vec[index]) largest = l;
else largest = index;
if (r <= last && vec[r] > vec[largest]) largest = r;

if (largest != index) {
swap(vec[largest], vec[index]);
maxHeapify(largest);
}
}
};

int main(void){
int x;
PriorityQueue pq;
string op = "no op";

while (op[2] != 'd') {
cin >> op;
if (op[2] == 's') {
// insert
cin >> x;
pq.insert(x);
}
else if (op[2] == 't') {
// extract
cout << pq.topAndPop() << endl;
}
}
return 0;
}


リモートフリーランス。ウェブサービス、スマホアプリエンジニア。

お仕事のご依頼・お問い合わせはこちら