public class HeapSort implements Sort {
    private int [] sorted;
    private int N;

    @Override
    public String getName() {
        return "Heap Sort";
    }

    @Override
    public int[] sort(int [] unsorted) {
        this.sorted = unsorted;
        this.N = unsorted.length-1;
        heapify();
        for(int i=N;i > 0; i--) {
            Utils.swap(sorted, 0, i);
            N = N-1;
            maxHeap(0);
        }
        return sorted;
    }

    private void heapify() {
        for(int i = N/2; i >= 0; i--) {
            maxHeap(i);
        }
    }

    private void maxHeap(int i) {
        int left = i * 2;
        int right = left + 1;
        int max = i;

        if (left <= N && sorted[left] > sorted[i]) {
            max = left;
        }

        if(right <= N && sorted[right] > sorted[max]) {
            max = right;
        }

        if (max != i) {
            Utils.swap(sorted, i, max);
            maxHeap(max);
        }
    }
}
