Nik_Perepelov

сектор приз

Dec 1st, 2021
1,132
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.  
  6. struct Heap {
  7.  
  8.     void addElement(int value) {
  9.         elements.push_back(value);
  10.         int i = elements.size() - 1;
  11.         while (elements[i]  < elements[(i - 1) / 2]) {
  12.             swap(elements[i], elements[(i - 1) / 2]);
  13.             i = (i - 1) / 2;
  14.         }
  15.     }
  16.  
  17.  
  18.     int getMax() {
  19.         int result = elements[0];
  20.         swap(elements[0], elements[size() - 1]);
  21.         elements.resize(size() - 1);
  22.         return result;
  23.     }
  24.  
  25.     int size() {
  26.         return elements.size();
  27.     }
  28.  
  29.     void heapify(int i) {
  30.         int left, right, largest;
  31.  
  32.         while (true) {
  33.             largest = i;
  34.             left = 2 * i + 1;
  35.             right = 2 * i + 2;
  36.  
  37.             if (left < size() && elements[left] < elements[largest]) {
  38.                 largest = left;
  39.             }
  40.  
  41.             if (right < size() && elements[right] < elements[largest]) {
  42.                 largest = right;
  43.             }
  44.  
  45.             if (largest == i) {
  46.                 break;
  47.             }
  48.  
  49.             swap(elements[largest], elements[i]);
  50.  
  51.             i = largest;
  52.         }
  53.     }
  54.  
  55.     vector<int> elements;
  56. };
  57.  
  58. int main() {
  59.     Heap heap;
  60.     int n;
  61.  
  62.     cin >> n;
  63.  
  64.     for (int i = 0; i < n; i++) {
  65.         int value;
  66.         cin >> value;
  67.  
  68.         heap.addElement(value);
  69.     }
  70.  
  71.     for (int i = n - 1; i >= 0; i--) {
  72.         cout << heap.getMax() << ' ';
  73.         heap.heapify(0);
  74.     }
  75.  
  76.     return 0;
  77. }
RAW Paste Data