Nik_Perepelov

12.2 Насте

Dec 1st, 2021
1,088
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. int num_v = 0;
  6. vector <int> vec;
  7.  
  8. void heapify(int i) { // приводим пирамиду к правильному виду
  9.     int greatestChild = i;
  10.     while (1) {
  11.         int element = 2 * i + 1;
  12.         if (element < num_v && vec[element] > vec[greatestChild])
  13.             greatestChild = element;
  14.         element++;
  15.         if (element < num_v && vec[element] > vec[greatestChild])
  16.             greatestChild = element;
  17.         if (greatestChild == i)
  18.             break;
  19.         swap(vec[greatestChild], vec[i]);
  20.         i = greatestChild;
  21.  
  22.     }
  23. }
  24.  
  25.  
  26. void addValue(int number) {
  27.     vec.push_back(number);
  28.     int actual = 0, p = 0;
  29.     actual = num_v;
  30.     p = (actual - 1) / 2;
  31.     while (actual > 0 && vec[actual] > vec[p]) {
  32.         swap(vec[actual], vec[p]);
  33.         actual = p;
  34.         p = (actual - 1) / 2;
  35.     }
  36. }
  37.  
  38.  
  39. void bigHeapify() {
  40.     for (int i = num_v / 2; i >= 0; i--)
  41.         heapify(i);
  42.     heapify(0);
  43. }
  44.  
  45. int popMax() {
  46.     int answer = vec[0];
  47.  
  48.     num_v-=1;
  49.     vec[0] = vec[num_v];
  50.     vec.erase(vec.end() - 1);
  51.     bigHeapify();
  52.     return answer;
  53. }
  54.  
  55. int main() {
  56.     int k;
  57.     cin >> k;
  58.     for (int i = 0; i < k; i++) {
  59.         int a;
  60.         cin >> a;
  61.         if (a == 1) {
  62.             int answer = popMax();
  63.             cout << answer << endl;
  64.         }
  65.         else {
  66.             int input;
  67.             cin >> input;
  68.             addValue(input);
  69.             num_v++;
  70.         }
  71.     }
  72.     return 0;
  73. }
RAW Paste Data