HeapSort | C ++ program for implementation of Heap Sort ; To heapify a subtree rooted with node i which is an index in arr [ ] . n is size of heap ; Initialize largest as root ; left = 2 * i + 1 ; right = 2 * i + 2 ; If left child is larger than root ; If right child is larger than largest so far ; If largest is not root ; Recursively heapify the affected sub - tree ; main function to do heap sort ; Build heap ( rearrange array ) ; One by one extract an element from heap ; Move current root to end ; call max heapify on the reduced heap ; A utility function to print array of size n ; Driver code
#include <iostream> NEW_LINE using namespace std ; void heapify ( int arr [ ] , int n , int i ) { int largest = i ; int l = 2 * i + 1 ; int r = 2 * i + 2 ; if ( l < n && arr [ l ] > arr [ largest ] ) largest = l ; if ( r < n && arr [ r ] > arr [ largest ] ) largest = r ; 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 ) ; } } void printArray ( int arr [ ] , int n ) { for ( int i = 0 ; i < n ; ++ i ) cout << arr [ i ] << " ▁ " ; cout << " STRNEWLINE " ; } int main ( ) { int arr [ ] = { 12 , 11 , 13 , 5 , 6 , 7 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; heapSort ( arr , n ) ; cout << " Sorted ▁ array ▁ is ▁ STRNEWLINE " ; printArray ( arr , n ) ; }