package com.sorts;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import static com.sorts.SortUtils.less;
import static com.sorts.SortUtils.swap;

public class HeapSort {

    private static class Heap {
        /**
         * Array to store heap
         */
        private T[] heap;

        /**
         * Constructor
         *
         * @param heap array of unordered integers
         */
        Heap(T[] heap) {
            this.heap = heap;
        }

        /**
         * Heapifies subtree from top as root to last as last child
         *
         * @param rootIndex index of root
         * @param lastChild index of last child
         */
        private void heapSubtree(int rootIndex, int lastChild) {
            int leftIndex = rootIndex * 2 + 1;
            int rightIndex = rootIndex * 2 + 2;
            T root = heap[rootIndex];
            if (rightIndex