SHARE
TWEET

Untitled

a guest Oct 22nd, 2019 71 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. void create_heap(int *arr, int root, int bottom){
  5.     int child;
  6.     while(root * 2 < bottom){
  7.         if(root * 2 == bottom){
  8.             child = root * 2;
  9.         }
  10.         else if (arr[root * 2] > arr[root * 2 + 1])
  11.             child = root * 2;
  12.         else {
  13.             child = root * 2 + 1;
  14.         }
  15.         if (arr[root] < arr[child]){
  16.             swap(arr[root], arr[child]);
  17.             root = child;
  18.         }
  19.         else return;
  20.     }
  21. }
  22.  
  23. void heap_sort(int *arr, int n){
  24.     for (int i = (n / 2) - 1; i >= 0; i--){
  25.         create_heap(arr, i, n);
  26.     }
  27.     for (int i = n - 1; i >= 1; i--)
  28.     {
  29.         swap(arr[0], arr[i]);
  30.         create_heap(arr, 0, i - 1);
  31.     }
  32. }
  33.  
  34. int main(){
  35.     freopen("sort.in", "r", stdin);
  36.     freopen("sort.out", "w", stdout);
  37.     int n;
  38.     cin>>n;
  39.     int *arr = new int[n];
  40.     for(int i=0; i<n; i++){
  41.         cin>>arr[i];
  42.     }
  43.     heap_sort(arr, n);
  44.     for(int i=0; i<n; i++){
  45.         cout<<arr[i]<<" ";
  46.     }
  47.     return 0;
  48. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top