HeapSort | 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 program
< ? php function heapify ( & $ arr , $ n , $ i ) { $ largest = $ i ; $ l = 2 * $ i + 1 ; $ 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 [ $ i ] = $ arr [ $ largest ] ; $ arr [ $ largest ] = $ swap ; heapify ( $ arr , $ n , $ largest ) ; } } function heapSort ( & $ arr , $ n ) { for ( $ i = $ n / 2 - 1 ; $ i >= 0 ; $ i -- ) heapify ( $ arr , $ n , $ i ) ; for ( $ i = $ n - 1 ; $ i > 0 ; $ i -- ) { $ temp = $ arr [ 0 ] ; $ arr [ 0 ] = $ arr [ $ i ] ; $ arr [ $ i ] = $ temp ; heapify ( $ arr , $ i , 0 ) ; } } function printArray ( & $ arr , $ n ) { for ( $ i = 0 ; $ i < $ n ; ++ $ i ) echo ( $ arr [ $ i ] . " ▁ " ) ; } $ arr = array ( 12 , 11 , 13 , 5 , 6 , 7 ) ; $ n = sizeof ( $ arr ) / sizeof ( $ arr [ 0 ] ) ; heapSort ( $ arr , $ n ) ; echo ' Sorted array is ' . " STRNEWLINE " ; printArray ( $ arr , $ n ) ; ? >