Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <cmath>
- #include <algorithm>
- using namespace std;
- int n = 0;
- vector <int> a;
- void MakeHeap(int i) {
- int max = i;
- while (true) {
- int element = 2 * i + 1;
- if (element < n && a[element] > a[max])
- max = element;
- element++;
- if (element < n && a[element] > a[max])
- max = element;
- if (max == i)
- break;
- else {
- swap(a[max], a[i]);
- i = max;
- }
- }
- }
- void HeapSort() {
- for (int i = n / 2; i >= 0; i--)
- MakeHeap(i);
- MakeHeap(0);
- }
- void Insert(int number) {
- a.push_back(number);
- int cur, p;
- cur = n;
- p = (cur - 1) / 2;
- while (cur > 0 && a[cur] > a[p]) {
- swap(a[cur], a[p]);
- cur = p;
- p = (cur - 1) / 2;
- }
- }
- int Extract() {
- int x = a[0];
- a[0] = a[n - 1];
- a.erase(a.begin() + n - 1);
- n--;
- HeapSort();
- return x;
- }
- int main() {
- int k, command, temp;
- cin >> k;
- for (int i = 0; i < k; ++i) {
- cin >> command;
- if (command == 0) {
- cin >> temp;
- Insert(temp);
- n++;
- }
- else
- cout << Extract() << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement