aoj

# ALDS1_9_C Priority Queue

ALDS1_9_C Priority Queue
Feb. 2, 2020, 1:52 p.m.

## 解答

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 #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 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; }