content: import java.util.Arrays;
  
  public class HeapSort {
  
      public static void sort(int[] arr) {
          int n = arr.length;
  
          // Build the max-heap from the array
          for (int i = n / 2 - 1; i >= 0; i--) {
              heapify(arr, n, i);
          }
  
          // Extract elements from the heap one by one
          for (int i = n - 1; i > 0; i--) {
              // Move the current root (largest element) to the end
              int temp = arr[0];
              arr[0] = arr[i];
              arr[i] = temp;
  
              // Call heapify on the reduced heap
              heapify(arr, i, 0);
          }
      }
  
      private static void heapify(int[] arr, int n, int i) {
          int largest = i;
          int leftChild = 2 * i + 1;
          int rightChild = 2 * i + 2;
  
          if (leftChild < n && arr[leftChild] > arr[largest]) {
              largest = leftChild;
          }
  
          if (rightChild < n && arr[rightChild] > arr[largest]) {
              largest = rightChild;
          }
  
          if (largest != i) {
              int swap = arr[i];
              arr[i] = arr[largest];
              arr[largest] = swap;
  
              heapify(arr, n, largest);
          }
      }
  
      public static void main(String[] args) {
          int[] data = {12, 11, 13, 5, 6, 7};
  
          System.out.println("Original array:");
          System.out.println(Arrays.toString(data));
  
          sort(data);
  
          System.out.println("\nSorted array:");
          System.out.println(Arrays.toString(data));
      }
  }