import java.util.Scanner; public class HeapSort { // ---------- Heapify Function ---------- public static void heapify(int[] arr, int n, int i) { int largest = i; // root int left = 2 * i + 1; // left child int right = 2 * i + 2; // right child // If left child is larger if (left < n && arr[left] > arr[largest]) { largest = left; } // If right child is larger if (right < n && arr[right] > arr[largest]) { largest = right; } // If largest is not root if (largest != i) { int temp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp; // Recursively heapify the affected subtree heapify(arr, n, largest); } } // ---------- Heap Sort Function ---------- public static void heapSort(int[] arr) { int n = arr.length; // Build max heap for (int i = n / 2 - 1; i >= 0; i--) { heapify(arr, n, i); } // Extract elements from heap one by one for (int i = n - 1; i > 0; i--) { // Move root to end int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; // Heapify reduced heap heapify(arr, i, 0); } } // ---------- Main Method ---------- public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.print("Enter size of array: "); int n = sc.nextInt(); int[] arr = new int[n]; System.out.println("Enter " + n + " elements:"); for (int i = 0; i < n; i++) { arr[i] = sc.nextInt(); } heapSort(arr); System.out.println("Sorted Array:"); for (int x : arr) { System.out.print(x + " "); } sc.close(); } }