nrk009

Heap

Oct 17th, 2020 (edited)
663
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
  5. #define ll long long
  6. #define ld long double
  7. #define pb push_back
  8. #define fe first
  9. #define se second
  10. #define nl "\n"
  11. #define pp pair < ll , ll >
  12. #define sz(x) (ll)x.size()
  13. #define st(x) sort(x.begin(),x.end())
  14. #define rst(x) sort(x.rbegin(), x.rend())
  15. #define all(x) x.begin(),x.end()
  16. long double pi = 3.14159265358979323;
  17.  
  18. const double EPS = 1e-12;
  19. const int N = 1e6 + 5;
  20. //Just A Gentle Reminder about MOD
  21. const int mod = 1e9 + 7;
  22.  
  23.  
  24. //Heap - Sort
  25.  
  26. //implementing max  - Heap
  27.  
  28. void Heapify(int n , vector < int > &arr , int index){
  29.  
  30.  
  31.         int smallest_index = index;
  32.         int left_child = smallest_index*2 + 1;
  33.         int right_child = smallest_index*2 + 2;
  34.         if(left_child < n && arr[left_child] > arr[smallest_index]){
  35.             smallest_index = left_child;
  36.         }
  37.         if(right_child < n && arr[right_child] > arr[smallest_index]){
  38.             smallest_index = right_child;
  39.         }
  40.  
  41.         if(index != smallest_index){
  42.             swap(arr[smallest_index] , arr[index]);
  43.             Heapify(n,arr,smallest_index);
  44.         }
  45.  
  46. }  
  47. //Time Complexity - O(nlogn) for heap sort
  48. //For making max heap or min heap O(n)
  49.  
  50. //Balanced Binary Tree(Complete Binary Tree)
  51.  
  52. void BuildHeap(int n , vector < int > &arr){
  53.  
  54.     int start_index = n/2 - 1;
  55.     for(int i = start_index ; i >= 0 ; i-- ){
  56.             Heapify(n,arr,i);
  57.     }
  58.    
  59.     /*for(int i = 0 ; i < n; i++ ){
  60.         cout << arr[i] << " ";
  61.     }*/
  62.    
  63.  
  64.     //Code Required for Heap - Sort
  65.     int heap_size = n ;
  66.     for(int i = n - 1 ; i > 0 ; i-- ){
  67.         swap(arr[i] , arr[0]);
  68.         heap_size -= 1;
  69.         Heapify(heap_size, arr , 0);
  70.     }
  71.  
  72.     for(int i = 0 ; i < n; i++ ){
  73.         cout << arr[i] << " ";
  74.     }
  75.  
  76. }  
  77. int main()
  78. {
  79.     fast;
  80.     int n;
  81.     cin >> n ;
  82.     vector < int > arr(n);
  83.     for(int i = 0 ; i < n; i++ ){
  84.         cin >> arr[i];
  85.     }    
  86.     BuildHeap(n,arr);
  87.    
  88.  
  89.  
  90.  
  91.  
  92.  
  93.  
  94.  
  95.  
  96.  
  97.  
  98.  
  99.  
  100.  
  101.  
  102.  
  103.  
  104.  
  105.  
  106.  
  107.  
  108.  
  109.    
  110.     return 0;
  111. //It's not end it yet
  112. }
RAW Paste Data