package Sorts;

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

import static Sorts.SortUtils.*;

/**
 * Heap Sort Algorithm
 * Implements MinHeap
 *
 * @author Podshivalov Nikita (https://github.com/nikitap492)
 */
public class HeapSort implements SortAlgorithm {


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

        /**
         * Constructor
         *
         * @param heap array of unordered integers
         */
        public 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