title: Restore heap condition throughout the entire heap
body: <p>I'm trying to answer the following programming question:</p>
  
  <p>In the heap.java program, the <code>insert()</code> method inserts a new node in the heap and ensures the heap condition is preserved. Write a <code>toss()</code> method that places a new node in the heap array without attempting to maintain the heap condition. (Perhaps each new item can simply be placed at the end of the array.) Then write a <code>restoreHeap()</code> method that restores the heap condition throughout the entire heap. Using <code>toss()</code> repeatedly followed by a single <code>restoreHeap()</code> is more efficient than using <code>insert()</code> repeatedly when a large amount of data must be inserted at one time. See the description of heapsort for clues. To test your program, insert a few items, toss in some more, and then restore the heap.</p>
  
  <p>I've written the code for the toss function which successfully inserts the node at the end and doesn't modify the heap condition. I'm having problems with the <code>restoreHeap</code> function though and I can't wrap my head around it. I've included the two functions below. </p>
  
  <p>The full code of heap.java is <a href="http://pastebin.com/XpBPhA0m" rel="nofollow">here</a> (includes <code>toss()</code> and <code>restoreHeap()</code> )</p>
  
  <p><code>toss()</code> - I based this off the insert function</p>
  
  <pre><code>public boolean toss(int key)
  {
      if(currentSize==maxSize)
          return false;
      Node newNode = new Node(key);
      heapArray[currentSize] = newNode;
      currentSize++;
      return true;
  }  // end toss()
  </code></pre>
  
  <p><code>restoreHeap()</code> - I based this off the trickleUp function and I'm getting a StackOverflowError.</p>
  
  <pre><code>public void restoreHeap(int index)
  {
      int parent = (index-1) / 2;
      Node bottom = heapArray[index];
  
      while( index &gt; 0 &amp;&amp;
              heapArray[parent].getKey() &lt; bottom.getKey() )
      {
          heapArray[index] = heapArray[parent];  // move it down
          index = parent;
          parent = (parent-1) / 2;
      }  // end while
      heapArray[index] = bottom;
      while(index != 0)
      {
          restoreHeap(parent++);
      }
  
  }  // end restoreHeap()
  </code></pre>
  
  <p>Any ideas? Help appreciated.</p>