在整个堆中恢复堆条件

Question

我正在尝试回答以下编程问题:

在heap.java程序中,该insert()方法在堆中插入一个新节点,并确保保留堆条件.编写一个toss()方法,将新节点放在堆数组中,而不尝试维护堆条件.(也许每个新项都可以简单地放在数组的末尾.)然后编写一个restoreHeap()方法来恢复整个堆中的堆状态.使用toss()多次,随后通过单个restoreHeap()比使用更有效的insert()反复当大量数据都必须在一个时间被插入.有关线索,请参阅heapsort的说明.要测试您的程序,请插入一些项目,再扔一些,然后还原堆.

我已经为折腾函数编写了代码,该函数在最后成功插入节点,并且不会修改堆条件.我遇到了这个restoreHeap功能的问题而我无法绕过它.我已经包含了以下两个功能.

heap.java的完整代码在这里(包括toss()和restoreHeap())

toss() - 我基于插入功能

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

restoreHeap() - 我基于trickleUp函数,我得到一个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()

有任何想法吗？帮助赞赏.

Answer 1

我会尝试一下。这是一种执行您要求的方法并附有一些解释。

由于您知道堆中所有节点的一半是叶子节点，并且叶子本身就是一个有效的堆，因此您只需运行另一半节点即可确保它们也有效。如果我们从底部向上执行此操作，则当我们向上遍历堆时，我们可以在“下方”维护一个有效的堆结构。这可以通过循环轻松完成for：

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

那么具体是如何restoreHeap实施的呢？它应该index对照其子节点检查节点，看看是否需要重新定位该节点。因为我们确保节点下面的树index是堆，所以我们只需要将index节点移动到正确的位置即可。因此我们将它移到树中。

首先我们需要找到孩子们。由于三行中的每一行的节点数量是前一行的两倍，因此可以这样定位子节点：

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

现在您只需将子节点的值与index节点值进行比较即可。如果子节点的值更大，则需要index与子节点交换该节点。如果两个孩子都有较大的值，则需要与两者中具有最大值的孩子进行交换（以保持交换后的堆结构）。交换节点后，您需要再次调用该方法以查看是否需要将index节点向下移动到树中。

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