5

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

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

我已经为 toss 函数编写了代码，该函数在末尾成功插入节点并且不修改堆条件。不过，我的功能有问题，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()

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

4

1 回答 1

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);
    }
}
于 2013-03-29T21:07:33.610 回答