title: How to write a bubbleDown method with Heap in Java?
body: <p>I know there are several questions like this posted all over stack overflow, however none really answer my question. I am writing a helper private bubbleDown method to help me sort on my public static HeapSort method. </p>
  
  <p>I know the Idea is to Treat a itself as a max-heap, whose data starts at 0 (not 1).</p>
  
  <ul>
  <li>a is not actually in heap order.</li>
  <li>But if you repeatedly "bubble down" each non-leaf node, starting from the last one, you will eventually have a proper heap.</li>
  </ul>
  
  <p>I've written this algorithm, however I'm not sure if this exactly works. </p>
  
  <pre><code>public class MaxHeapPriorityQueue&lt;E extends Comparable&lt;E&gt;&gt;
  {
  private E[] elementData;
  private int size;
  
  @SuppressWarnings("unchecked")
  public MaxHeapPriorityQueue()
  {
      elementData = (E[]) new Comparable[10];
      size = 0;
  }
  public static void heapSort(Comparable[] a, int size)
  {
      MaxHeapPriorityQueue mhpq = new MaxHeapPriorityQueue();
      mhpq.elementData = a;
      mhpq.size = size;
      for (Comparable n : a)
      {
          mhpq.bubbleDown((int) n);
      }
      for (int i = 0; i &lt; a.length-1; i++)
      {
          a[i] = mhpq.sortRemove();
      }
  }
  private void bubbleDown(int index)
  {
      boolean found = false;
      while(!found)
      {
          int leftIndex = lChild(index);
          int rightIndex = rightChild(index);
          int largestChildIndex = leftIndex;
  
          if(hasRChild(index))
          {
  
       if(elementData[leftIndex].compareTo(elementData[rightIndex]) &lt; 0 )
       {
          largestChildIndex = rightIndex;
       }
  }
          if(hasLChild(index))
          {
  
     if(elementData[largestChildIndex].compareTo(elementData[index]) &gt; 0)
              {
                  swap(elementData, largestChildIndex , index);
                  index = largestChildIndex;
              }
              else
              {
                  found = true;
              }
          }
          else //Probably a leaf
          {
              found = true;
          }
      }
  }
  </code></pre>
  
  <p>Now everything seems to running more smoothly, it's just when I have duplicate values, they are not ordered correctly. I am failing to find this error in my bubble method. </p>