package Sort;

import java.util.Scanner;

public class HeapSort {
    
    /**
     * build a max heap 
     * @param a 
     * @param size
     */
    public static void buildMaxHeap(int a[], int size) {
        for(int i = size/2; i > 0; i--) {
            maxHeapify(a, i, size);
        }
    }
    
    public static void maxHeapify(int a[], int i, int size) {
        int leftNode = 2 * i;
        int rightNode = 2 * i + 1;
        int largestNode = i;
        if(leftNode <= size && a[leftNode] > a[i]) {
            largestNode = leftNode;
        }
        if(rightNode <= size && a[rightNode] > a[largestNode]) {
            largestNode = rightNode;
        }
        if(largestNode != i) {
            int temp = a[i];
            a[i] = a[largestNode];
            a[largestNode] = temp;
            maxHeapify(a, largestNode, size);
        }
    }
    
    /**
     * print the current array
     * @param a
     * @param size
     */
    public static void printArray(int a[], int size) {
        for(int i = 1; i <= size; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println("");
    }
    

    public static void heapSort(int a[], int size) {
        buildMaxHeap(a, size);
        printArray(a, size);
        
        int len = size;
        for(int i = size; i >= 2; i--) {
            int temp = a[i];
            a[i] = a[1];
            a[1] = temp;
            len--;
            maxHeapify(a, 1, len);
            System.out.println("The intermediate result: ");
            printArray(a, size);
        }
    }
    
    public static void main(String args[]) {
        @SuppressWarnings("resource")
        Scanner scan = new Scanner(System.in);
        System.out.println("The size: ");
        int size = scan.nextInt();
        int a[] = new int[size+1];
        System.out.println("Input the elements: ");
        for(int i = 1 ; i <= size; i++) {
            a[i] = scan.nextInt();
        }
        heapSort(a, size);
        System.out.println("The final result: ");
        printArray(a, size);
    }
}