在整个堆中恢复堆条件

Question

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

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

我已经为toss函数编写了代码，该函数成功地将节点插入到结尾处，并且不修改堆条件。不过，我在使用restoreHeap函数时遇到了问题，我不能完全理解它。我已经包含了下面的两个函数。

heap.java的完整代码是here (包括toss()和restoreHeap() )

toss() -I基于insert函数

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