Restore heap condition throughout the entire heap

Question

I'm trying to answer the following programming question:

In the heap.java program, the insert() method inserts a new node in the heap and ensures the heap condition is preserved. Write a toss() 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 restoreHeap() method that restores the heap condition throughout the entire heap. Using toss() repeatedly followed by a single restoreHeap() is more efficient than using insert() 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.

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 restoreHeap function though and I can't wrap my head around it. I've included the two functions below.

The full code of heap.java is here (includes toss() and restoreHeap() )

toss() - I based this off the insert function

public boolean toss(int key)
{
    if(currentSize==maxSize)
        return false;
    Node newNode = new Node(key);
    heapArray[currentSize] = newNode;
    currentSize++;
    return true;
}  // end toss()

restoreHeap() - I based this off the trickleUp function and I'm getting a StackOverflowError.

public void restoreHeap(int index)
{
    int parent = (index-1) / 2;
    Node bottom = heapArray[index];

    while( index > 0 &&
            heapArray[parent].getKey() < 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()

Any ideas? Help appreciated.

Answer 1

I'll give it a shot. Here is a way to do what you asked with some explanation.

Since you know that half of all nodes in a heap are leafs and a leaf, by itself, is a valid heap, you only have to run through the other half of the nodes to make sure they also are valid. If we do this from the bottom and up, we can maintain a valid heap structure "below" as we go up through the heap. This can easily be accomplished by a for loop:

 public void rebuildHeap()
 {
    int half = heapArray.length / 2;
    for(int i = half; i >= 0; i--)
        restoreHeap(i);
 }

How is restoreHeap implemented then? It's supposed to check the node at index against its children to see if it needs to relocate the node. Because we make sure that the trees below the index node are heaps, we only have to move the index node to the right position. Hence we move it down in the tree.

First we need to locate the children. Since each row in the three have twice as many nodes as the row before, the children can be located like this:

private void restoreHeap(int index)
{
    int leftChild = (index * 2) + 1;  //+1 because arrays start at 0
    int rightChild = leftChild +1;
    ...

Now you just have to compare the childrens value against your index nodes value. If a child have a bigger value you need to swap the index node with the child node. If both children have a bigger value, you need to swap with the child with the biggest value of the two (to maintain the heap structure after the swap). When the nodes have been swapped you need to call the method again to see if you need to move the index node further down the tree.

    ...
    int biggest = index;
    if(leftChild < currentSize && heapArray[leftChild].getKey() > heapArray[index].getKey())
        biggest = leftChild;  //LeftChild is bigger
    if(rightChild < currentSize && heapArray[rightChild].getKey() > heapArray[biggest].getKey())
        biggest = rightChild; //RightChild is bigger than both leftChild and the index node

    if(biggest != index) //If a swap is needed
    {
        //Swap
        Node swapper = heapArray[biggest];
        heapArray[biggest] = heapArray[index];
        heapArray[index] = swapper;

        restoreHeap(biggest);
    }
}