/*
  * PriorityQueueTest2faster.java
 * SORTED INSERT ARRAY IMPLEMENTATION WITH ADDITIVE INCREMENT, resizing while inserting
 * Created on October 10, 2012, 3:44 PM
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */


package priorityqueuetest;


/**
 *
 * @author suchenek
 */
public class PriorityQueueTest2faster {


//    /** Creates a new instance of PriorityQueueTest */
//    public PriorityQueueTest() {
// }

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
           int[] Array;
           int N;
 for (N = 1; N<=100; N++)
 {
        Array = new int[N];
        for (int i = 0; i < N; i++)
        Array[i] = (int)(Math.sqrt(97)*(13*i + 1)*(19*i + 2)+i - 17)%1000;
        for (int i = 0; i < N; i++)
        Array[i] = -i;

        for (int i = 0; i < N; i++) System.out.print(Array[i] + " ");
        System.out.println();
        cnt.clr(); //counts moves of keys while sorting
        cnt2.clr(); //counts moves of keys while resizing
        Bcnt.clrAll(); //counts comparisons of keys while sorting
        PriorityQueueSort(Array);
        for (int i = 0; i < N; i++) System.out.print(Array[i] + " ");
        System.out.println();
//        Tcomp(N) is the sorting "time" measured by the number of comparisons
//        of keys
        System.out.print("Tcomp(" + N +")");
        Bcnt.out(" = ");
        System.out.print("  " + (N*(N-1)/2) + " = N*(N-1)/2");
//        Tmov(N) is the sorting "time" measured by the number of moves
//        of keys, not including resizing
        System.out.print("  Tmov(" + N +")");
        cnt.out(" = ");
        System.out.println("  " + (2*N + N*(N-1)/2) + " = 2*N + N*(N-1)/2");
//        R(N) is the resizing "time"
        System.out.print("R(" + N +")");
        cnt2.out(" = ");
        System.out.println("  " +
        (5*(((int)Math.ceil(N/5.)-2)*((int)Math.ceil(N/5.)+1))
                )
//               - 5*((int)Math.ceil(N/5.)-2))
                + " = 5*(((int)Math.ceil(N/5.)-2)*((int)Math.ceil(N/5.)+1))"
//               + "-5*((int)Math.ceil(N/5.)-2)"
                );
//        The total cost of resizing is twice the cost of upsizing because the cost of
//        upsizing is the same as the cost of downsizing:
//        5*(ceil(N/5) - 2)(ceil(N/5) + 1)
//        If the cost of downsizing is k*5 less than the cost of upsizing (in a faster version of remove)
//        then the total cost of resizing is:
//        5*(ceil(N/5) - 2)(ceil(N/5) + 1) - 5*(ceil(N/5) - 2).
 }
}
    public static void  PriorityQueueSort(int[] A)
    {
        int n = A.length;
        PriorityQueue2faster PQ = new PriorityQueue2faster();
        for (int i = 0; i < n; i++) PQ.insert(A[i]);
//        System.out.println("A Size of PQ is " + PQ.Length());
        for (int i = n-1; i >= 0; i--) A[i]=PQ.remove();
//        for (int i = 0; i < n; i++) A[i]=PQ.remove();
//        System.out.println("B Size of PQ is " + PQ.Length());

    }

}