import java.util.Random;
import java.util.Scanner;

///////////////////////////////////////////
//
// Test frame for CS2 recitation assignments
//   Created 12-10-2014 by Rick Leinecker
//
///////////////////////////////////////////

public class CSRecitationWeek2
{

    ///////////////////////////////////////////
    //
    // Start of assignment code.
    //
    ///////////////////////////////////////////

    /**
     * Returns the last name, first name, and PID of the student.
     *
     * This is required in order to get credit for the programming assignment.
     */
    static String GetNameAndPID()
    {
        return( "Ashwas,Rubba,r3430968");
    }

    static int[] DoBubbleSort( int[] DataIn )
    {
        //temp variable for storing the lesser element
        int temp;
        //first for-loop starts at second element
        for(int i=1; i < DataIn.length; i++ )
        {
        //second for-loop starts at first element
            for(int j=0; j < DataIn.length-1; j++)
            {
                //swap whenever the previous element is bigger than a following element
                if(DataIn[j] > DataIn[i])
                {
                    temp = DataIn[i];
                    DataIn[i] = DataIn[j];
                    DataIn[j] = temp;
                }
            }
        }
        //return sorted array
        return DataIn;
    }

        static int[] DoInsertSort( int[] DataIn )
    {
        //declare variables
        int insert,j,i;
        //start loop at second element
        for( i=1; i < DataIn.length; i++)
        {
            //set the element at i to the variable insert (number to be inserted)
            insert = DataIn[i];
            //set j to i
            j=i;
            //loop until j=0 and while insert is less than the previous element
            while(j>=1 && insert<DataIn[j-1])
            {
                //move larger numbers down
                DataIn[j]=DataIn[j-1];
                //decrement
                j--;
            }

            //insert value
            DataIn[j] = insert;

        }

        //return sorted array
        return DataIn;
    }

        static int[] DoHeapSort( int[] DataIn )
    {

        return DataIn;
    }

    // The heap (min-heap).
    static int[] nHeap;

    // Randomly generated numbers to be used as input.
    static int[] nRandomNumbers;

    // The size of the heap, nHeap. The size of the heap may be smaller than
    // nHeap.length. The heap is comprised of the elements at indexes between 0
    // and heapSize-1 of nHeap.
    static int heapSize;

    // Methods to get index of parent, left child, and right child of node at
    // index nIndex of the heap  (zero-based index). The indexes outputed by
    // GetLeft and GetRight must be verified to actually exist within the heap
    // (use heapSize to determine this).

    private static int GetParentIndex(int nIndex)
    {
        int parent;
        parent = nIndex/2;

        return parent;
    }

    static int GetLeft( int nIndex )
    {
        int left;
        left = nIndex*2;

        return left;
    }

    static int GetRight( int nIndex )
    {
        int right;
        right = nIndex*2 + 1;

        return right;
    }

    // Function to swap two numbers in an array. Auxiliary method to SiftUp and
    // Heapify.
        public static void swap(int arr[], int i, int j)
        {
            int temp;
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }

    static void BuildHeap()
    {
        // Input: static field nHeap, an array of ints, representing a full
        // binary tree (not a BST), except for the last level which may be
        // only partially filled from the left

        // Input: static field heapSize

        // Output: modified nHeap such that it represents a min-heap

        // Complexity: O(heapSize)

        // Start at the parent of the last node (i.e., the right-most,
        // bottom-most node in the tree that is not a leaf)
        //    - the last node is heapSize - 1
        //    - the parent of any node is (nodeIdx - 1) / 2
        //    - therefore the parent of the last node is
        //      (heapSize - 2) / 2
        //    - equivalent to GetParentIndex(heapSize-1)

        // Algorithm:

        // for i = GetParentIndex(heapSize-1) DOWN TO  0:
        //      Heapify(i)

        nHeap = new int[nRandomNumbers.length];
        for( int i=0; i<nRandomNumbers.length; i++ )
        {
            AddElement(i);
        }

    }


    static void Heapify( int nIndex )
    {
        // Input: static field nHeap, an array of ints, representing a full
        // binary tree (not a BST), except for the last level which may be
        // only partially filled from the left

        // Input: nIndex, an index into nHeap

        // Output: modified nHeap such that element nIndex has been "sifted
        // down" until that element is less than its children or that element
        // is a leaf

        // Another name for this method might be "SiftDown".

        // Algorithm:


        // If nIndex is a leaf node (has no children), then there is nothing to
        // do (use heapSize to determine this)
         if(heapSize==1)
             return;

        int smallest=nHeap[nIndex];
        int leftIdx = GetLeft(nIndex);
        int rightIdx = GetRight(nIndex);

        if(nHeap[leftIdx] < nHeap[nIndex])
            smallest = nHeap[leftIdx];
        if(nHeap[rightIdx] < nHeap[nIndex])
            smallest = nHeap[leftIdx];

        // smallest <- either the index leftIdx, rightIdx, or nIndex whose
        // corresponding heap node value is the smallest out of these three
        // (however, ensure that leftIdx and rightIdx are actually children;
        // use heapSize to determine this)

        if(smallest != nIndex)

        // if smallest != nIndex:
        //    COMMENT: This means the node at nIndex has a child smaller than
        //    itself at index smallest. This smallest child needs to come up
        //    and replace the node at nIndex, and the node at nIndex needs to
        //    come down to replace the smallest child. We then repeat the
        //    process recursively at index smallest.

        //    swap node values at indexes smallest and nIndex
            Heapify(smallest);
    }


    // The following methods, AddElement and its auxiliary method SiftUp, are
    // not used with DoHeapSort.

    // DoHeapSort uses BuildHeap instead, which is a more efficient way (O(n))
    // to build a heap starting from a list of numbers than AddElement. The way
    // to build a heap using AddElement is to start with an empty heap and
    // repeatedly add each element into the heap. This way is O(nlogn).
    // However, AddElement is useful to add new elements into an existing heap
    // once it has been built with BuildHeap.

    static void AddElement( int nNumber )
    {
        // Input: static fields nHeap, heapSize. nHeap must already be a valid
        // min-heap.

        // Input: nNumber, a new node to add to the heap

        // Output: heap with nNumber added, heapSize increased by 1

        // Complexity: O(log(heapSize))
        if(heapSize+1 > nHeap.length)
        {
              int[] doubleArray;
              doubleArray = new int[2*(nHeap.length)];
              for(int i=0; i<nHeap.length; i++)
                  doubleArray[i]=nHeap[i];


            heapSize++;
            doubleArray[heapSize-1]=nNumber;
            SiftUp(heapSize-1);

        }

        else {
        heapSize++;
        nHeap[heapSize-1]=nNumber;
        SiftUp(heapSize-1);
             }

        // Precondition: heapSize+1 <= nHeap.length
        // If this is not the case, before running the algorithm, create a new
        // array that is double the size of nHeap, copy the elements of nHeap
        // into it, and assign nHeap to be the new larger array

        // Algorithm:

        // Increase heapSize by 1
        // Copy nNumber to index heapSize-1 of the heap
        // SiftUp(heapSize-1)
    }

    static void SiftUp( int nNodeIndex )
    {
        // repeatedly sift up the element at nNodeIndex as long as its parent
        // node is greater or the element is the root (this is similar to
        // Heapify but it moves the element upwards instead of downwards)

        int index, temp;
        if( nNodeIndex != 0 )
        {
            // Get the parent index so that we can
            index = GetParentIndex( nNodeIndex );

            //compare parent with the number at the specified index
            if( nHeap[index] > nHeap[nNodeIndex] )
            {
                // Swap the parent and child.
                temp = nHeap[index];
                nHeap[index] = nHeap[index];
                nHeap[nNodeIndex] = temp;

                // recursively call to sort
                SiftUp(index);
            }
        }

    }

    ///////////////////////////////////////////
    //
    // End of assignment code.
    //
    ///////////////////////////////////////////

    public static void setRandomArray(int n)
    {
        Random rnd = new Random();
        nRandomNumbers = new int[n];
        for( int i=0; i<nRandomNumbers.length; i++ )
        {
            nRandomNumbers[i] = rnd.nextInt( 500 );
        }
    }

    public static void main(String[] args)
    {
            System.out.println();
        System.out.println();

        int[] array = {1,5,2,1,4,6};
        DoBubbleSort(array);
        System.out.println("BubbleSort:");
        for(int y=0; y<array.length; y++)
            System.out.printf("%d ",array[y]);

        System.out.println();
        System.out.println();

        int[] array2 = {1,5,2,10,4,6,5,2,10,3,5,6};
        DoInsertSort(array2);
        System.out.println("InsertSort:");
        for(int y=0; y<array2.length; y++)
            System.out.printf("%d ",array2[y]);

        BuildHeap();
    }
}