Nik_Perepelov

Гениальная куча

Nov 30th, 2021
777
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. int n = 0;
  8. vector <int> a;
  9.  
  10. void MakeHeap(int i) {
  11.     int max = i;
  12.     while (true) {
  13.         int element = 2 * i + 1;
  14.         if (element < n && a[element] > a[max])
  15.             max = element;
  16.         element++;
  17.         if (element < n && a[element] > a[max])
  18.             max = element;
  19.         if (max == i)
  20.             break;
  21.         else {
  22.             swap(a[max], a[i]);
  23.             i = max;
  24.         }
  25.     }
  26. }
  27.  
  28. void HeapSort() {
  29.     for (int i = n / 2; i >= 0; i--)
  30.         MakeHeap(i);
  31.     MakeHeap(0);
  32. }
  33.  
  34. void Insert(int number) {
  35.     a.push_back(number);
  36.     int cur, p;
  37.     cur = n;
  38.     p = (cur - 1) / 2;
  39.     while (cur > 0 && a[cur] > a[p]) {
  40.         swap(a[cur], a[p]);
  41.         cur = p;
  42.         p = (cur - 1) / 2;
  43.     }
  44. }
  45.  
  46. int Extract() {
  47.     int x = a[0];
  48.     a[0] = a[n - 1];
  49.     a.erase(a.begin() + n - 1);
  50.     n--;
  51.     HeapSort();
  52.     return x;
  53. }
  54.  
  55. int main() {
  56.     int k, command, temp;
  57.     cin >> k;
  58.     for (int i = 0; i < k; ++i) {
  59.         cin >> command;
  60.         if (command == 0) {
  61.             cin >> temp;
  62.             Insert(temp);
  63.             n++;
  64.         }
  65.         else
  66.             cout << Extract() << endl;
  67.     }
  68.     return 0;
  69. }
  70.  
  71.  
  72.  
RAW Paste Data