Nik_Perepelov

насте

Dec 1st, 2021
942
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5. int n;
  6.  
  7. vector<int> a;
  8.  
  9. void siftDown(int i) {
  10.     while (2 * i + 1 < n) {
  11.         // heapSize — количество элементов в куче
  12.         int l = 2 * i + 1, r = 2 * i + 2;
  13.         int j = l;
  14.         if (r < n && a[r] < a[l]) {
  15.             j = r;
  16.         }
  17.         if (a[i] <= a[j])
  18.             break;
  19.         swap(a[i], a[j]);
  20.         i = j;
  21.     }
  22. }
  23.  
  24. void siftUp(int i) {
  25.     while (a[i]  < a[(i - 1) / 2]) {
  26.         swap(a[i], a[(i - 1) / 2]);
  27.         i = (i - 1) / 2;
  28.     }
  29. }
  30.  
  31. void insert(int key) {
  32.     n++;
  33.     a[n - 1] = key;
  34.     siftUp(n - 1);
  35. }
  36.  
  37. void buildHeap() {
  38.     for (int i = n / 2; i >= 0; i--) {
  39.         siftDown(i);
  40.     }
  41. }
  42.  
  43. int ext(){
  44.     int ans = a[0];
  45.     a[0] = a[n - 1];
  46.     n--;
  47.     siftDown(0);
  48.     return ans;
  49. }
  50.  
  51. int main() {
  52.     n = 0;
  53.     int k;
  54.     cin >> k;
  55.     a.resize(k);
  56.     for (int i = 0; i < k; i++) {
  57.         int v;
  58.         cin >> v;
  59.         insert(v);
  60.     }
  61.  
  62.     for (int i = 0; i < k; i++){
  63.         cout << ext() << ' ';
  64.     }
  65. }
  66.  
RAW Paste Data