content: /*
    Heap Sort
    Implementation of Heap Sort in Java which uses max heap
  */
  
  public class HeapSort
  {
      public void sort(int arr[])
      {
          int n = arr.length;
  
          // Step 1: Build heap (rearrange array)
          for (int i = n / 2 - 1; i >= 0; i--)
              heapify(arr, n, i);
  
          // Step 2: Extract elements one by one from heap
          for (int i=n-1; i>=0; i--)
          {
              // Step 2.1: Move current root to end
              int temp = arr[0];
              arr[0] = arr[i];
              arr[i] = temp;
  
              // Step 2.2: Call max heapify on the reduced heap
              heapify(arr, i, 0);
          }
      }
      /*  Method to heapify a subtree rooted with node i which is
  
          an index in arr[].
          Heap Size = n
      */
      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[] = {19, 13, 15, 8, 9, 7};
          int n = arr.length;
  
          HeapSort ob = new HeapSort();
          ob.sort(arr);
  
          System.out.println("Sorted array is");
          printArray(arr);
      }
  }
  