Category : Java | Sub Category : Java Programs | By Prasad Bonam Last updated: 2021-04-19 09:09:51 Viewed : 475
Heap sort is a comparison based sorting technique based on Binary Heap data structure. It is similar to selection sort where we first find the maximum element and place the maximum element at the end. Then repeat the same process for the remaining element. Let’s write the program and understand its working.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 | package runnerdev; public class HeapSort { public void sort( int arr[]) { int n = arr.length; // Build heap (rearrange array) for ( int i = n / 2 - 1 ; i >= 0 ; i--) heapify(arr, n, i); // One by one extract an element from heap for ( int i=n- 1 ; i>= 0 ; i--) { // Move current root to end int temp = arr[ 0 ]; arr[ 0 ] = arr[i]; arr[i] = temp; // call max heapify on the reduced heap heapify(arr, i, 0 ); } } void heapify( int arr[], int n, int i) { int largest = i; // Initialize largest as root int l = 2 *i + 1 ; // left = 2*i + 1 int r = 2 *i + 2 ; // right = 2*i + 2 // If left child is larger than root if (l< n && arr[l] >arr[largest]) largest = l; // If right child is larger than largest so far if (r < n && arr[r] > arr[largest]) largest = r; // If largest is not root if (largest != i) { int swap = arr[i]; arr[i] = arr[largest]; arr[largest] = swap; // Recursively heapify the affected sub-tree heapify(arr, n, largest); } } /* A utility function to print array of size n */ static void printArray( int arr[]) { int n = arr.length; for ( int i= 0 ; i<n; ++i) System.out.print(arr[i]+ " " ); System.out.println(); } // Driver program public static void main(String args[]) { int arr[] = { 12 , 11 , 13 , 5 , 6 , 7 }; int n = arr.length; HeapSort ob = new HeapSort(); ob.sort(arr); System.out.println( "Sorted array is" ); printArray(arr); } } |
1 | 5 , 6 , 7 , 11 , 12 , 13 |