Princeton1/module8/src/main/java/com/hithomelabs/princeton1/module8/HeapSort.java

package com.hithomelabs.princeton1.module8;

import com.hithomelabs.princeton1.module5.MeasurableHelper;
import com.hithomelabs.princeton1.module5.MeasurableSort;
import com.hithomelabs.princeton1.module5.SortingMetaData;

import java.util.Comparator;


public class HeapSort<E> implements MeasurableSort<E>, MeasurableHelper {

    @Override
    public void sort(E[] arr, Comparator<E> cmp, SortingMetaData metaData) {
        int N = arr.length;
        E[] heapArr = (E[]) new Object[N+1];
        // * * to simplify we copy original array from
        System.arraycopy(arr, 0, heapArr, 1, N);
        // * * An array of size N holds a heap of size N-1
        if (metaData != null)
            metaData.startTime();
        coreSortingLogic(heapArr, N, cmp, metaData);
        if (metaData != null)
            metaData.endTime();
        System.arraycopy(heapArr, 1, arr, 0, N);
    }

    public static <T> void heapify(T[] arr){
        int N = arr.length;
        T[] heapArr = (T[]) new Object[N+1];
        // * * to simplify we copy original array from
        System.arraycopy(arr, 0, heapArr, 1, N);
        // * * An array of size N holds a heap of size N-1
        for (int i = N/2; i >= 1; i--)
            Heap.sink(heapArr, i, N, null, null);
        System.arraycopy(heapArr, 1, arr, 0, N);
    }

    private void coreSortingLogic(E[] arr, int N, Comparator<E> cmp, SortingMetaData metaData) {
        // * * Converting array to max-heap an array in place
        for (int i = N/2; i >= 1; i--)
            Heap.sink(arr, i, N, cmp, metaData);
        // * * After converting to max-heap, in every iteration remove the max element of the heap
        while(N > 1){
            MeasurableHelper.exch(arr, 1, N--, metaData);
            Heap.sink(arr, 1, N, cmp, metaData);
        }
    }


    @Override
    public void sort(E[] arr, Comparator<E> cmp) {
        int N = arr.length;
        E[] heapArr = (E[]) new Object[N+1];
        // * * to simplify we copy original array from
        System.arraycopy(arr, 0, heapArr, 1, N);

        // * * An array of size N holds a heap of size N-1
        coreSortingLogic(heapArr, N, cmp, null);
        System.arraycopy(heapArr, 1, arr, 0, N);
    }

    @Override
    public void sort(E[] arr) {
        int N = arr.length;
        E[] heapArr = (E[]) new Object[N+1];
        // * * to simplify we copy original array from
        System.arraycopy(arr, 0, heapArr, 1, N);

        // * * An array of size N holds a heap of size N-1
        coreSortingLogic(heapArr, N,null, null);
        System.arraycopy(heapArr, 1, arr, 0, N);
    }

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