Iterative HeapSort | Java implementation of Iterative Heap Sort ; function build Max Heap where value of each child is always smaller than value of their parent ; if child is bigger than parent ; swap child and parent until parent is smaller ; swap value of first indexed with last indexed ; maintaining heap property after each swapping ; if left child is smaller than right child point index variable to right child ; if parent is smaller than child then swapping parent with child having higher value ; A utility function to print array of size n ; Driver program
public class HeapSort { static void buildMaxHeap ( int arr [ ] , int n ) { for ( int i = 1 ; i < n ; i ++ ) { if ( arr [ i ] > arr [ ( i - 1 ) / 2 ] ) { int j = i ; while ( arr [ j ] > arr [ ( j - 1 ) / 2 ] ) { swap ( arr , j , ( j - 1 ) / 2 ) ; j = ( j - 1 ) / 2 ; } } } } static void heapSort ( int arr [ ] , int n ) { buildMaxHeap ( arr , n ) ; for ( int i = n - 1 ; i > 0 ; i -- ) { swap ( arr , 0 , i ) ; int j = 0 , index ; do { index = ( 2 * j + 1 ) ; if ( index < ( i - 1 ) && arr [ index ] < arr [ index + 1 ] ) index ++ ; if ( index < i && arr [ j ] < arr [ index ] ) swap ( arr , j , index ) ; j = index ; } while ( index < i ) ; } } public static void swap ( int [ ] a , int i , int j ) { int temp = a [ i ] ; a [ i ] = a [ j ] ; a [ j ] = temp ; } static void printArray ( int arr [ ] ) { int n = arr . length ; for ( int i = 0 ; i < n ; i ++ ) System . out . print ( arr [ i ] + " ▁ " ) ; System . out . println ( ) ; } public static void main ( String args [ ] ) { int arr [ ] = { 10 , 20 , 15 , 17 , 9 , 21 } ; int n = arr . length ; System . out . print ( " Given ▁ array : ▁ " ) ; printArray ( arr ) ; heapSort ( arr , n ) ; System . out . print ( " Sorted ▁ array : ▁ " ) ; printArray ( arr ) ; } }