/* CS 2110, discussion 2: Example of inconsistent formatting. */

import java.util.Arrays;

/**
 * A priority queue of integers.  Provides constant-time access to the largeset integer in the queue and supports logarithmic-time insertion and removal of elements.  Also provides a means of sorting integer arrays in ascending order.  Implemented using a binary max-heap.
 */
class IntHeap
{
    /** Backing store for values in the queue.  Capacity may exceed size.  May be replaced with a larger array if insertion is requested when store is full. */
    int[] values;
    /** Number of elements currently stored in the queue.  Must be less than or equal to length of values. */
    int SIZE;

    /**
     * Construct a new instance of an IntHeap.
     * Backing store will be allocated with the requested capacity, but
     * queue will be logically empty.
     * @param capacity Initial capacity of backing store
     */
    IntHeap(int capacity) {
        if (capacity < 0) { throw new IllegalArgumentException("Capacity must be non-negative"); }
            values = new int[capacity];
    }

    /** Duh. */
    int size() { return SIZE; }

    /** If element at index i is smaller than children, swap with largest child and recurse. */
    void bubbleDown(int i)
    {
        int c1= 2 * i+1;  // Left child
        if((c1 >= SIZE)) return;  // Base case
          int c2= c1 + 1;  // Right child
        int cMax= c1;  // Index of largest child
        if (((c2 < SIZE) && (values[c2] > values[c1])))
        cMax= c2;
        if (values[i] < values[cMax]) {
            swap(i, cMax);
        bubbleDown(cMax);
    }
}

    /** Remove and return largest element in queue.
     * @return largest element in queue
     */
    int Pop() {
      if(SIZE==0){throw new NoSuchElementException("Cannot pop from empty heap");}
      int ans=values[0];
      swap(0,--SIZE);
      bubbleDown(0);
      return ans;
    }

    /** Insert new element into queue.
     * @param x Element to insert into queue
     */
    void push(int x)
      {
        if(SIZE == values.length)
          {
            values = Arrays.copyOf(values, 2*values.length);
          }
        values[SIZE++] = x;
        bubbleUp(SIZE-1);
      }

    /**
     * Permute elements of an array so they are sorted (in-place) in ascending order.
     * @param a Array to sort
     */
    static void Sort(int[] a) {
        IntHeap h=new IntHeap(0);
        h.values=a;
        for(int i=0;i<a.length;i+=1) h.push(a[i]);
        while((h.size()>0))
        a[h.size()-1]=h.pop();
    }

	void swap(int i,int j) {
		int tmp = values[i];
		values[i] = values[j];
		values[j] = tmp;
	}

    /** Do the bubble-up. */
    void bubbleUp(int i) {
        int p= (i-1) / 2;
        if ((values[p]<values[i])) {
            swap(p,i);
        bubbleUp(p);
      }
   }
}