heapsort.cpp

/* 
Heap sort is a comparison based sorting technique based on Binary Heap data structure.
It is an in-place algorithm.
Time complexity of Heap Sort is O(nlogn).
*/

#include <iostream> 
using namespace std; 
  
void heapify(int arr[], int n, int i) 
{ 
    int largest = i; //here largest is the root
    int left = 2*i + 1; 
    int right = 2*i + 2; 
  
    if (left < n && arr[left] > arr[largest]) 
        largest = left; 

    if (right < n && arr[right] > arr[largest]) 
        largest = right; 
  
    if (largest != i) 
    { 
        swap(arr[i], arr[largest]); 
        heapify(arr, n, largest); 
    } 
} 
  
void heapSort(int arr[], int n) 
{ 
    for (int i=n/2-1; i>=0; i--) 
        heapify(arr, n, i); 
 
    for (int i=n-1; i>=0; i--) 
    { 
        swap(arr[0], arr[i]); 
        heapify(arr, i, 0); 
    } 
} 

int main() 
{ 
    int n;
    cin>>n;
    int arr[n];
    for(int i=0;i<n;i++)
        cin>>arr[i];
        
    heapSort(arr, n); 
  
    cout << "Sorted array : "; 
    for(int i=0;i<n;i++)
        cout<<arr[i]<<" ";
    cout<<endl;
    return 0;
}