// Introduction to Algorithms
// Template for Heap CLASS - 
// do HeapUp, HeapDown, Heapify & HeapSort first!
// <put your name, login name & student number here>

class Heap {
      private int capacity;
      private int contents;
      private int [ ] array;

      final static int ROOT = 0;
      public int root () { return ROOT; }
      private int parent      (int child)  { return ???; }
      private int left_child  (int parent) { return ???; }
      private int right_child (int parent) { return ???; }
      private int sibling     (int child)  { return ???; }

      private int choice = 0;
      public void choice (int c) { choice=c; }

      // make a new heap with contents=0 and capacity=size
      public Heap (int size) {
         ???
      }

      // make a new heap with default size
      public Heap () { this (10); }

      // make a new heap by heafifying a given array
      public Heap (int[ ] data) {
         ???
      }

      // transfer the heap to a bigger array (cf. jugs)
      private void rebuild (int new_size) {
         ???
      }

      private sift_up (int position) {
         ???
      }

      private sift_down (int position) {
         ???
      }

      public void insert (int new_value) {
         ???
      }

      public int delete_root () {
         ???
      }

      private void heapify () {
         ???
      }

      public int[ ] sort_me () {
         ???
      }

      // use a "new Heap" so that your class "implements Sorting"
      public int[ ] sort (int[ ] array) {
         ???
      }

      // maybe write your own (command line) user interface
      public static void main (String[ ] args) {
         ???
      }
}