title: How do i implement heapSort on my heap?
body: <p>Okay so this is one of my last assignments and of course this is creating the most stress for me but the only thing keeping me from turning this assignment in is being able to apply heapsort on the Heap that the user inputs their own integer values into an array list which is displayed and here is the code for that: </p>
  
  <p>The heap propgram works fine but the Heapsort doesn't work or i can't use it or make a call for it in the HeapApp class</p>
  
  <pre><code>  import java.lang.reflect.Array;
  import java.util.ArrayList;
  import java.util.NoSuchElementException;
  import java.util.Scanner;
  
  
  
  /**
   */
  public class Heap&lt;T extends Comparable&lt;T&gt;&gt; {
  
      private ArrayList&lt;T&gt; items;
  
      public Heap() {
          items = new ArrayList&lt;T&gt;();
      }
  
      private void siftUp() {
          int k = items.size() - 1;
          while (k &gt; 0) {
              int p = (k-1)/2;
              T item = items.get(k);
              T parent = items.get(p);
              if (item.compareTo(parent) &gt; 0) {
                  // swap
                  items.set(k, parent);
                  items.set(p, item);
  
                  // move up one level
                  k = p;
              } else {
                  break;
              }
          }
      }
  
      public void insert(T item) {
          items.add(item);
          siftUp();
      }
  
      private void siftDown() {
          int k = 0;
          int l = 2*k+1;
          while (l &lt; items.size()) {
              int max=l, r=l+1;
              if (r &lt; items.size()) { // there is a right child
                  if (items.get(r).compareTo(items.get(l)) &gt; 0) {
                      max++;
                  }
              }
              if (items.get(k).compareTo(items.get(max)) &lt; 0) {
                      // switch
                      T temp = items.get(k);
                      items.set(k, items.get(max));
                      items.set(max, temp);
                      k = max;
                      l = 2*k+1;
              } else {
                  break;
              }
          }
      }
  
      public T delete() 
      throws NoSuchElementException {
          if (items.size() == 0) {
              throw new NoSuchElementException();
          }
          if (items.size() == 1) {
              return items.remove(0);
          }
          T hold = items.get(0);
          items.set(0, items.remove(items.size()-1));
          siftDown();
          return hold;
      }
  
      public int size() {
          return items.size();
      }
  
      public boolean isEmpty() {
          return items.isEmpty();
  
      }
  
      public String toString() {
          return items.toString();
      }
  
  //----------------------------------------------------------------------------------------------------------------------------------------
  
  
      public class Heapsort&lt;T extends Comparable&lt;T&gt;&gt; {
            /**
             * Sort the array a[0..n-1] by the heapsort algorithm.
             * 
             * @param a the array to be sorted
             * @param n the number of elements of a that have valid values
             */
            public void sort(T[] a, int n) {
              heapsort(a, n - 1);
            }
  
            /**
             * Sort the ArrayList list by the heapsort algorithm.
             * Works by converting the ArrayList to an array, sorting the
             * array, and converting the result back to the ArrayList.
             * 
             * @param list the ArrayList to be sorted
             */
            public void sort(ArrayList&lt;T&gt; items) {
              // Convert list to an array.
              @SuppressWarnings("unchecked")
              T[] a = (T[]) items.toArray((T[]) Array.newInstance(items.get(0).getClass(), items.size()));
  
              sort(a, items.size());   // sort the array
  
              // Copy the sorted array elements back into the list.
              for (int i = 0; i &lt; a.length; i++)
                items.set(i, a[i]);
            }
  
            /**
             * Sort the array a[0..lastLeaf] by the heapsort algorithm.
             * 
             * @param items the array holding the heap
             * @param lastLeaf the position of the last leaf in the array
             */
            private void heapsort(T[] items, int lastLeaf) {
              // First, turn the array a[0..lastLeaf] into a max-heap.
              buildMaxHeap(items, lastLeaf);
  
              // Once the array is a max-heap, repeatedly swap the root
              // with the last leaf, putting the largest remaining element
              // in the last leaf's position, declare this last leaf to no
              // longer be in the heap, and then fix up the heap.
              while (lastLeaf &gt; 0) {
                swap(items, 0, lastLeaf);       // swap the root with the last leaf
                lastLeaf--;                 // the last leaf is no longer in the heap
                maxHeapify(items, 0, lastLeaf); // fix up what's left
              }
            }
  
            /**
             * Restore the max-heap property. When this method is called, the max-heap
             * property holds everywhere, except possibly at node i and its children. When
             * this method returns, the max-heap property holds everywhere.
             * 
             * @param items the array holding the heap
             * @param i index of the node that might violate the max-heap property
             * @param lastLeaf the position of the last leaf in the array
             */
            private void maxHeapify(T[] items, int i, int lastLeaf) {
              int left = leftChild(i);    // index of node i's left child
              int right = rightChild(i);  // index of node i's right child
              int largest;  // will hold the index of the node with the largest element
                            // among node i, left, and right
  
              // Is there a left child and, if so, does the left child have an
              // element larger than node i?
              if (left &lt;= lastLeaf &amp;&amp; items[left].compareTo(items[i]) &gt; 0)
                largest = left; // yes, so the left child is the largest so far
              else
                largest = i;    // no, so node i is the largest so far
  
              // Is there a left child and, if so, does the right child have an
              // element larger than the larger of node i and the left child?
              if (right &lt;= lastLeaf &amp;&amp; items[right].compareTo(items[largest]) &gt; 0)
                largest = right; // yes, so the right child is the largest
  
              // If node i holds an element larger than both the left and right
              // children, then the max-heap property already held, and we need do
              // nothing more. Otherwise, we need to swap node i with the larger
              // of the two children, and then recurse down the heap from the larger
              // child.
              if (largest != i) {
                swap(items, i, largest);
                maxHeapify(items, largest, lastLeaf);
              }
            }
  
            /**
             * Form array a[0..lastLeaf] into a max-heap.
             * 
             * @param items array to be heapified
             * @param lastLeaf position of last valid data in a
             */
            private void buildMaxHeap(T[] items, int lastLeaf) {
              int lastNonLeaf = (lastLeaf - 1) / 2; // nodes lastNonLeaf+1 to lastLeaf are leaves
              for (int j = lastNonLeaf; j &gt;= 0; j--)
                maxHeapify(items, j, lastLeaf);
            }
  
            /**
             * Swap two locations i and j in array a.
             * 
             * @param items the array
             * @param i first position
             * @param j second position
             */
            private void swap(T[] items, int i, int j) {
              T t = items[i];
              items[i] = items[j];
              items[j] = t;
            }
  
            /**
             * Return the index of the left child of node i.
             * 
             * @param i index of the parent node
             * @return index of the left child of node i
             */
            private int leftChild(int i) {
              return 2 * i + 1;
            }
  
            /**
             * Return the index of the right child of node i.
             * 
             * @param i index of the parent node
             * @return the index of the right child of node i
             */
            private int rightChild(int i) {
              return 2 * i + 2;
            }
  
            /**
             * For debugging and testing, print out an array.
             * 
             * @param a the array to print
             * @param n number of elements of a to print
             */
            public void printArray(T[] items, int n) {
              for (int i = 0; i &lt; n; i++)
                System.out.println(items[i]);
            }
  
  }
  }
  
      import java.util.Scanner;
  
  public class HeapApp{
  /**
   * @param args
   */
  public static void main(String[] args) {
      Heap&lt;Integer&gt; hp = new Heap&lt;Integer&gt;();
  
      Scanner sc = new Scanner(System.in);
  
  
      System.out.print("Enter next int, 'done' to stop: ");
      String line = sc.next();
      while (!line.equals("done")) {
          hp.insert(Integer.parseInt(line));
          System.out.println(hp);
          System.out.print("Enter next int, 'done' to stop: ");
          line = sc.next();
      }
  
      while (hp.isEmpty()) {
          //int max = hp.delete();
          System.out.println( " " + hp);
  
      }
  
      System.out.println(hp);
  
      System.out.println("After sorting " + hp);
  
  
  
  }
  
  
  }
  </code></pre>
  
  <p>Now i'm not asking anyone to do it for me but i just need help figuring out how to get the Heapsort to work with the heap PLEASE HELP! The most i have tried is setting the parameters within the Heap sort method. </p>
  
  <p>My question and code is not a duplicate for one this is based on a Heap and heapsort from the user input: </p>
  
  <pre><code>public static void main(String[] args) {
      Heap&lt;Integer&gt; hp = new Heap&lt;Integer&gt;();
  
      Scanner sc = new Scanner(System.in);
  
  
      System.out.print("Enter next int, 'done' to stop: ");
      String line = sc.next();
      while (!line.equals("done")) {
          hp.insert(Integer.parseInt(line));
          System.out.println(hp);
          System.out.print("Enter next int, 'done' to stop: ");
          line = sc.next();
      }
  </code></pre>
  
  <p>Also the entire Heap is implemented using an ArrayList: </p>
  
  <pre><code> public class Heap&lt;T extends Comparable&lt;T&gt;&gt; {
  
          private ArrayList&lt;T&gt; items;
  
          public Heap() {
              items = new ArrayList&lt;T&gt;();
          }
  </code></pre>