import java.util.*;
public class HeapSort {
    static ArrayList<Integer> heap_sort(ArrayList<Integer> arr) {
        heapSort(arr, arr.size());
        return arr;
    }
    static void heapify(ArrayList<Integer> arr, int n, int i){

        //   Collections.swap(arr, random, i);
        int smallest = i; //init smallest root
        int l = 2 * i +1; //lef side of heap
        int r = 2 * i +2;  //right side of heap

        //if child is smaller than root
        if ((l < n) && (arr.get(l) > arr.get(smallest))){
            smallest = l;
        }
        if (r < n && arr.get(r) > arr.get(smallest)) {
            smallest = r;
        }
        //if child  is not root
        if (smallest != i) {
            int temp = arr.get(i);
            Collections.swap(arr, i, smallest);
            heapify(arr, n, smallest);
        }
    }
    static void heapSort(ArrayList<Integer> arr, int n){
        for(int i = n / 2 -1; i >= 0; i--){
            heapify(arr, n, i);
        }
        for(int i = n -1; i >= 0; i--){
            Collections.swap(arr, 0, i);
            heapify(arr, i, 0);
        }
    }

}