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);

}

}

}