/*
 *  The address of the HTML version this page is:
 *  http://csc.csudh.edu/suchenek/MakeHeap.html
 */                            



/**
 * Copyright: Marek A. Suchenek 2012 and other parties
 * @author Suchenek at csudh dot edu
 *
 *
 * The use for the purpose of classroom
 * instruction or scientific research
 * is allowed with proper attribution
 * to the copyright holder or holders.
 *
 * This Java program runs under NetBeans 6.9
 *
 * An analysis of this program has been published in:
 *
 * Suchenek, M.A. :
 * "Elementary Yet Precise Worst-Case Analysis of Floyd's Heap-Construction Program,"
 * Fundamenta Informaticae 120 (2012), pp 75--92,
 * doi: 10.3233/FI-2012-751 (link http://dx.doi.org/10.3233/FI-2012-751)
 *
 */

package heap;

public class MakeHeap {
    private int N; //the number of elements in the heap
    private int[] heap; //the heap; itemArray[0] is not a part of the heap and is used as an auxiliary variable

    private void FixHeap(int q)
    {
        int x = heap[q]; //x is the root of the almost subheap that may have to be demoted
        while (2*q <= N) //q, the initial index of x, is not the index of a leaf
        {
        int lp = 2*q; //lp is the index of the first child of q
        if (lp < N) //the second child exists
        {
            if (heap[lp+1] > heap[lp]) //the second child is larger than the first child
                lp++; //lp is the index of the larger child
        }
            if (x >= heap[lp]) //x is not lesser than any of its children
            {
                heap[q] = x; //so, x belongs at index q and the heap is fixed.
                return;
            }
            heap[q] = heap[lp]; //promote the larger child
            q = lp; //demote x
        }
        heap[q]=x; //x has been demoted to an index of leaf and so the heap is fixed.
    }

    public MakeHeap(int[] elements) // constructor
    {
        N = elements.length - 1; // elements[0] is not used for sorting
        heap = elements; // intentional side effect
        for (int i = N/2; i > 0; i--)
            FixHeap(i);
    }

    public int RemoveMax()
    {
     if (N==0) return -9999;
     //here count != 0
        int maxItem = heap[1]; //remove the root and
        heap[1] = heap[N]; //fill the vacancy with the last element
        N--;
        FixHeap(1);
        return maxItem;
        }

    public void RemoveAll()
    {
        for (int i = N; i > 0; i--)
            heap[i] = RemoveMax();
    }

    public static void Heapsort(int[] array)
    {
        MakeHeap H = new MakeHeap(array);
        H.RemoveAll();
    }

    public static void main(String[] args)
    {
        int[] Array;
        for (int N = 0; N<=21; N++)
        {
            Array = new int[N + 1]; //Array[0] is not used for sorting
            for (int i = 1; i <= N; i++)
                Array[i] = (int)(Math.sqrt(97)*(13*i + 1)*(19*i + 2)+i - 17)%1000;
//            for (int i = 1; i <= N; i++)
//                Array[i] = -i;
            System.out.println("N = " + N);
            System.out.println("Array to be sorted:");
            for (int i = 1; i <= N; i++)
                System.out.print(Array[i] + " ");
            System.out.println();

            Heapsort(Array);

            System.out.println("Sorted array:");
            for (int i = 1; i <= N; i++)
                System.out.print(Array[i] + " ");
                System.out.println();
        }
    }
}
/*
run:
N = 0
Array to be sorted:

Sorted array:

N = 1
Array to be sorted:
879
Sorted array:
879
N = 2
Array to be sorted:
879 621
Sorted array:
621 879
N = 3
Array to be sorted:
879 621 229
Sorted array:
229 621 879
N = 4
Array to be sorted:
879 621 229 702
Sorted array:
229 621 702 879
N = 5
Array to be sorted:
879 621 229 702 40
Sorted array:
40 229 621 702 879
N = 6
Array to be sorted:
879 621 229 702 40 243
Sorted array:
40 229 243 621 702 879
N = 7
Array to be sorted:
879 621 229 702 40 243 312
Sorted array:
40 229 243 312 621 702 879
N = 8
Array to be sorted:
879 621 229 702 40 243 312 247
Sorted array:
40 229 243 247 312 621 702 879
N = 9
Array to be sorted:
879 621 229 702 40 243 312 247 46
Sorted array:
40 46 229 243 247 312 621 702 879
N = 10
Array to be sorted:
879 621 229 702 40 243 312 247 46 711
Sorted array:
40 46 229 243 247 312 621 702 711 879
N = 11
Array to be sorted:
879 621 229 702 40 243 312 247 46 711 241
Sorted array:
40 46 229 241 243 247 312 621 702 711 879
N = 12
Array to be sorted:
879 621 229 702 40 243 312 247 46 711 241 637
Sorted array:
40 46 229 241 243 247 312 621 637 702 711 879
N = 13
Array to be sorted:
879 621 229 702 40 243 312 247 46 711 241 637 898
Sorted array:
40 46 229 241 243 247 312 621 637 702 711 879 898
N = 14
Array to be sorted:
879 621 229 702 40 243 312 247 46 711 241 637 898 24
Sorted array:
24 40 46 229 241 243 247 312 621 637 702 711 879 898
N = 15
Array to be sorted:
879 621 229 702 40 243 312 247 46 711 241 637 898 24 15
Sorted array:
15 24 40 46 229 241 243 247 312 621 637 702 711 879 898
N = 16
Array to be sorted:
879 621 229 702 40 243 312 247 46 711 241 637 898 24 15 872
Sorted array:
15 24 40 46 229 241 243 247 312 621 637 702 711 872 879 898
N = 17
Array to be sorted:
879 621 229 702 40 243 312 247 46 711 241 637 898 24 15 872 595
Sorted array:
15 24 40 46 229 241 243 247 312 595 621 637 702 711 872 879 898
N = 18
Array to be sorted:
879 621 229 702 40 243 312 247 46 711 241 637 898 24 15 872 595 182
Sorted array:
15 24 40 46 182 229 241 243 247 312 595 621 637 702 711 872 879 898
N = 19
Array to be sorted:
879 621 229 702 40 243 312 247 46 711 241 637 898 24 15 872 595 182 635
Sorted array:
15 24 40 46 182 229 241 243 247 312 595 621 635 637 702 711 872 879 898
N = 20
Array to be sorted:
879 621 229 702 40 243 312 247 46 711 241 637 898 24 15 872 595 182 635 953
Sorted array:
15 24 40 46 182 229 241 243 247 312 595 621 635 637 702 711 872 879 898 953
N = 21
Array to be sorted:
879 621 229 702 40 243 312 247 46 711 241 637 898 24 15 872 595 182 635 953 137
Sorted array:
15 24 40 46 137 182 229 241 243 247 312 595 621 635 637 702 711 872 879 898 953
BUILD SUCCESSFUL (total time: 0 seconds)
*/