Nik_Perepelov

пирамидальная сортировка

Dec 1st, 2021
733
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. class Pyramid {
  7.     int n;
  8.     vector<int> arr;
  9.  
  10.     void siftDown(int root, int bottom) {
  11.         int maxChild;
  12.         bool done = false;
  13.         while ((root * 2 <= bottom) && (!done)) {
  14.             if (root * 2 == bottom || arr[root * 2] > arr[root * 2 + 1]) {
  15.                 maxChild = root * 2;
  16.             } else {
  17.                 maxChild = root * 2 + 1;
  18.             }
  19.             if (arr[root] < arr[maxChild]) {
  20.                 swap(arr[root], arr[maxChild]);
  21.                 root = maxChild;
  22.             } else {
  23.                 done = true;
  24.             }
  25.         }
  26.     }
  27.  
  28. public:
  29.  
  30.     explicit Pyramid(const vector<int> &_arr) {
  31.         arr = _arr;
  32.         n = _arr.size();
  33.     }
  34.  
  35.     void sort() {
  36.         for (int i = (n / 2); i >= 0; i--)
  37.             siftDown(i, n - 1);
  38.         for (int i = n - 1; i >= 1; i--) {
  39.             swap(arr[0], arr[i]);
  40.             siftDown(0, i - 1);
  41.         }
  42.     }
  43.  
  44.     vector<int> getSorted() {
  45.         return arr;
  46.     }
  47. };
  48.  
  49. int main() {
  50.     int n;
  51.     cin >> n;
  52.     vector<int> v(n);
  53.     for (int &i: v)
  54.         cin >> i;
  55.  
  56.     Pyramid pyramid(v);
  57.     pyramid.sort();
  58.     v = pyramid.getSorted();
  59.  
  60.     for (int &i: v)
  61.         cout << i << ' ';
  62.  
  63.  
  64. }
RAW Paste Data