Heap Sort in Java
Below is the implementation of Heap Sort in Java:
Java
// Java program for implementation of Heap Sort 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 ); } } // To heapify a subtree rooted with node i which is // an index in arr[]. n is size of heap 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); } } |
Complexity of the above program:
Time Complexity : O(N log N), here N is number of elements in array.
Auxiliary Space : O(1), since no extra space used.
Java Program for Heap Sort
Heap sort is a comparison-based sorting technique based on the Binary Heap data structure. It is similar to the selection sort where first find the maximum element and place it at the end. We repeat the same process for the remaining element.