HeapSort.java

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 printArr(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[] = { 4, 23, 6, 78, 1, 54, 231, 9, 12 };
        int n = arr.length;
        System.out.println("The original Heap sort is: ");
        printArr(arr);
    
        HeapSort heapSort = new HeapSort();
        heapSort.sort(arr);
    
        System.out.println("The sorted array is");
        printArr(arr);
      }
}