heapsort

import java.util.*;
class HeapSort{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter the array size");
        int n = sc.nextInt();
        int arr[] = new int[n];
        for(int x = 0; x < n; x++){
            arr[x] = sc.nextInt();
        }
        for (int x = n / 2 - 1; x >= 0; x--){
            HeapSort.heapify(arr, n, x);
        }
        for (int x = n - 1; x > 0; x--){
            int temp = arr[0];
            arr[0] = arr[x];
            arr[x] = temp;
            HeapSort.heapify(arr, x, 0);
        }
        System.out.println(Arrays.toString(arr));

    }
    public static void heapify(int arr[], int n, int i){
        int largest = i;
        int l = 2 * i + 1;
        int r = 2 * i + 2;

        if(l < n && arr[l] > arr[largest]){
            largest = l;
        }
        if(r < n && arr[r] > arr[largest]){
            largest = r;
        }
        if(largest != i){
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;
            heapify(arr, n, largest);
        }

    }
}