java - 在整个堆中还原堆条件

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

在heap.java程序中，insert()方法在堆中插入一个新节点，并确保保留堆条件。编写一个toss()方法，该方法将新节点放置在堆数组中，而无需尝试维护堆条件。 (也许每个新项都可以简单地放在数组的末尾。)然后编写restoreHeap()方法，该方法可以在整个堆中恢复堆条件。当必须一次插入大量数据时，重复使用toss()和单个restoreHeap()会比重复使用insert()更有效。有关线索，请参见heapsort的描述。要测试您的程序，请插入一些项目，再扔一些，然后恢复堆。

我已经为toss函数编写了代码，该函数成功在最后插入了节点，并且没有修改堆条件。我在使用restoreHeap函数时遇到问题，无法解决这个问题。我在下面包括了两个功能。

heap.java的完整代码是here(包括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()

有任何想法吗？帮助表示赞赏。

最佳答案

我会试一试。这是一种通过一些解释来完成您所要求的方法。

由于您知道堆中所有节点的一半是叶子，而叶子本身就是有效堆，因此您只需要遍历另一半节点以确保它们也是有效的。如果从头到尾执行此操作，则在向上浏览堆时，我们可以在“下面”维护有效的堆结构。这可以通过for循环轻松完成:

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

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

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

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

现在，您只需要比较childs的值和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);
    }
}