Geek asks and answers

Restore heap state in whole heap

I am trying to answer the following programming question:

In the heap.java program, the method insert()inserts a new node into the heap and ensures that the state of the heap is preserved. Write a method toss()that puts the new node in the heap array without trying to save the state of the heap. (Perhaps each new element can simply be placed at the end of the array.) Then write a method restoreHeap()that restores the state of the heap in the entire heap. Reuse toss(), followed by single use restoreHeap(), is more efficient than reuse insert()when you need to insert a large amount of data at a time. See heapsort description for tips. To test your program, insert a few elements, add a few more, and then restore the heap.

I wrote code for a throw function that successfully inserts a node at the end and does not change the state of the heap. I have problems with the function restoreHeap, although I cannot wrap myself around it. I have included two functions below.

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

toss() - I based this on 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 on the trickleUp function, and I get 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 evaluate.

+5
source share
1 answer

I will do it. Here is a way to do what you asked for, with some explanation.

, - , , , , . , "", . for:

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

restoreHeap? node index , , node. , index node , index node . , .

. , , :

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

childrens index. , index node node. , ( ). , , , index node .

    ...
    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);
    }
}
+1

More articles:


All Articles