/**
 * An implementation of a minimum heap with handles
 */

public class Heap {

    private HeapElt[] array;
    int heapsize;
    int arraysize;

    /*
      The constructor has been set up with an initial array of size 4
      so that your doubleHeap() method will be tested.  Don't change
      this!
    */
    public Heap() {
	array = new HeapElt[4];
	heapsize = 0;
	arraysize = 4;
    }



    /*
      Exchanges that values at positions pos1 and pos2 in the heap array.
      Handles must be exchanged correctly as well.

      Running time = O(????)
    */
    private void exchange(int pos1, int pos2) {

	// PROVIDE YOUR IMPLEMENTATION HERE

    }



    /*
      Doubles the size of the array.  A new array is created, the elements in
      the heap are copied to the new array, and the array data member is set
      to the new array.  Data member arraysize is set to the size of the
      new array.

      Running time = O(????)
    */
    private void doubleHeap() {

	// PROVIDE YOUR IMPLEMENTATION HERE

    }



    /*
      Fixes the heap if the value at position pos may be smaller than its
      parent.  Using exchange() to swap elements will simplify your
      implementation.  Heap elements contain records that are Comparable;
      you will need to figure out what to test and how to test it.

      Running time = O(????)
    */
    public void heapifyUp(int pos) {

	// PROVIDE YOUR IMPLEMENTATION HERE

    }

    /*
      Fixes the heap if the value at position pos may be bigger than one of
      its children.  Using exchange() to swap elements will simplify your
      implementation.  Heap elements contain records that are Comparable;
      you will need to figure out what to test and how to test it.

      Running time = O(????)
    */
    public void heapifyDown(int pos) {

	// PROVIDE YOUR IMPLEMENTATION HERE

    }



    /*
      Insert inElt into the heap.  Before doing so, make sure that there is
      an open spot in the array for doing so.  If you need more space, call
      doubleHeap() before doing the insertion.

      Running time = O(????) (NOTE that there are a couple of different cases
      here!)
    */
    public void insert(HeapElt inElt) {

	// PROVIDE YOUR IMPLEMENTATION HERE

    }



    /*
      Remove the minimum element from the heap and return it.  Restore
      the heap to heap order.  Assumes heap is not empty, and will
      cause an exception if the heap is empty.

      Running time = O(????)
    */
    public HeapElt removeMin() {
	// WARNING: Will fail with empty heap!

	// PROVIDE YOUR IMPLEMENTATION HERE

    }



    /*
      Return the number of elements in the heap..

      Running time = O(????)
    */
    public int getHeapsize() {

	// PROVIDE YOUR IMPLEMENTATION HERE

    }

 

   /*
      Print out the heap for debugging purposes.  It is recommended to 
      print both the key from the record and the handle.

      Running time = O(????)
    */
    public void printHeap() {

	// PROVIDE YOUR IMPLEMENTATION HERE

     }

}