import java.util.Scanner;

public class HS {
        public void heapSort(int[] arr) {
                int n = arr.length;

                for (int i = n / 2 - 1; i >= 0; i--) {
                        heapify(arr, n, i);
                }

                for (int i = n - 1; i > 0; i--) {
                        swap(arr, 0, i);
                        heapify(arr, i, 0);
                }
        }

        private void heapify(int[] arr, int n, int i) {
                int largest = i;
                int left = 2 * i + 1;
                int right = 2 * i + 2;

                if (left < n && arr[left] > arr[largest]) {
                        largest = left;
                }

                if (right < n && arr[right] > arr[largest]) {
                        largest = right;
                }

                if (largest != i) {
                        swap(arr, i, largest);
                        heapify(arr, n, largest);

                }
        }

        private void swap(int[] arr, int i, int j) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
        }

        public void printArray(int[] arr) {
                for (int x : arr) {
                        System.out.print(x + " ");
                }
                System.out.println();
        }

        public static void main(String[] args) {
                Scanner scanner = new Scanner(System.in);
                HS heapSort = new HS();

                System.out.print("Enter the size of the array: ");
                int size = scanner.nextInt();

                int[] arr = new int[size];

                System.out.println("Enter " + size + " elements: ");
                for (int i = 0; i < size; i++) {
                        arr[i] = scanner.nextInt();
                }

                System.out.print("Original array: ");
                heapSort.printArray(arr);

                heapSort.heapSort(arr);
                System.out.print("Enter the size of the array: ");
                heapSort.printArray(arr);
        }
}