import java.util.Scanner;

/**
 * Sorting using heap sort.
 *
 * @author Mark Young (A00000000)
 */
public class HeapSort {

    /**
     * biggest number in list
     */
    private static final int BIGGEST = 1000;
    
    /**
     * keyboard scanner for whole program
     */
    private static final Scanner kbd = new Scanner(System.in);

    public static void main(String[] args) {
        // print introduction
        System.out.print("\n\n"
                + "Heap Sort\n"
                + "---------\n\n"
                + "This program uses heap sort to sort an array.\n\n");

        // Create list
        System.out.print("How long should I make the list? ");
        int numElts = kbd.nextInt();
        kbd.nextLine();
        int[] anArray = new int[numElts];
        for (int i = 0; i < numElts; i++) {
            anArray[i] = (int) (BIGGEST * Math.random());
        }

        // show list before sorting
        System.out.println("\nArray values before sorting:");
        PrintTrace.printArray(anArray);
        pause();

        // sort the list
        sort(anArray);

        // show list after sorting
        System.out.println("\nArray values after sorting:");
        PrintTrace.printArray(anArray);
        pause();
    }

    /**
     * Use heap sort to sort an array.
     *
     * @param a the array to be sorted
     */
    public static void sort(int[] a) {
        // maxHeapify
        System.out.println("Changing the list into a max-heap:");
        for (int i = a.length / 2; i > 0; --i) {
            System.out.println("Shifting " + a[i - 1] + " down...");
            percolateDown(a, i, a.length);
            PrintTrace.printHeap(a, i - 1, a.length);
            pause();
        }

        // report heap
        System.out.println("\nArray values as a max-heap:");
        PrintTrace.printHeap(a);
        pause();

        // removeAll
        System.out.println("Removing front items to back:");
        int numInHeap = a.length;
        while (numInHeap > 1) {
            --numInHeap;
            System.out.println("Moving " + a[0] + " to the back...");
            int temp = a[0];
            a[0] = a[numInHeap];
            a[numInHeap] = temp;
            percolateDown(a, 1, numInHeap);
            PrintTrace.printHeap(a, 0, numInHeap);
            pause();
        }
    }

    /**
     * Help build a REVERSE heap (largest items come out first). Move the item
     * from a[n] toward the back until it's larger than its children.
     *
     * @param a the array we're building the reverse heap in
     * @param n the position we're percolating from (1-based!!!)
     * @param len the length of the heap (or of the array we're building into a
     * heap)
     */
    private static void percolateDown(int[] a, int n, int len) {
        int temp = a[n - 1];
        while (2 * n <= len) {
            int l = largerChild(a, n, len);
            if (a[l - 1] > temp) {
                a[n - 1] = a[l - 1];
                n = l;
            } else {
                break;
            }
        }
        a[n - 1] = temp;
    }

    /**
     * Find the larger child of position n in array a. NOTE: 1-based indexing,
     * so the array indexes are one less than the heap positions.
     *
     * @param a the array the heap is in
     * @param n the heap position (1-based) of the parent
     * @param len the length of the heap (or of the array we're building into a
     * heap)
     * @return the heap position (1-based) of the larger child
     */
    private static int largerChild(int[] a, int n, int len) {
        if (2 * n == len) {
            return 2 * n;
        }
        return (a[2 * n - 1] > a[2 * n]) ? 2 * n : 2 * n + 1;
    }

    /**
     * Wait for the user to press the enter key.
     */
    public static void pause() {
        System.out.print("\n...Press ENTER...");
        kbd.nextLine();
        System.out.println();
    }

}