Heap Sort for decreasing order using min heap | To heapify a subtree rooted with node i which is an index in arr [ ] . n is size of heap ; Initialize smalles as root ; left = 2 * i + 1 ; right = 2 * i + 2 ; If left child is smaller than root ; If right child is smaller than smallest so far ; If smallest 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
function heapify ( arr , n , i ) { var smallest = i ; var l = 2 * i + 1 ; var r = 2 * i + 2 ; if ( l < n && arr [ l ] < arr [ smallest ] ) smallest = l ; if ( r < n && arr [ r ] < arr [ smallest ] ) smallest = r ; if ( smallest != i ) { [ arr [ i ] , arr [ smallest ] ] = [ arr [ smallest ] , arr [ i ] ] heapify ( arr , n , smallest ) ; } } function heapSort ( arr , n ) { for ( var i = parseInt ( n / 2 - 1 ) ; i >= 0 ; i -- ) heapify ( arr , n , i ) ; for ( var i = n - 1 ; i >= 0 ; i -- ) { [ arr [ 0 ] , arr [ i ] ] = [ arr [ i ] , arr [ 0 ] ] heapify ( arr , i , 0 ) ; } } function printArray ( arr , n ) { for ( var i = 0 ; i < n ; ++ i ) document . write ( arr [ i ] + " " ) ; document . write ( " " ) ; } var arr = [ 4 , 6 , 3 , 2 , 9 ] ; var n = arr . length ; heapSort ( arr , n ) ; document . write ( " " ) ; printArray ( arr , n ) ;