2 
void ReheapDown( int* heap, int top, int swpIndx, int numElements )  {
    int leftChild = 2 * top + 1;
    int rightChild = 2 * top + 2;
    int minChild;
    if (leftChild < numElements) {
        // find subscript of smallest child
        if (rightChild >= swpIndx || heap[leftChild] < heap[rightChild])
            minChild = leftChild;
        else
            minChild = rightChild;
        // if data at top is greater than smallest
        // child then swap and continue
        if (heap[top] > heap[minChild]) {
            swap( heap[top], heap[minChild] );
            ReheapDown( heap, minChild, swpIndx, numElements );
        }
    }

这是一个简单的堆。ReheapDown 部分用于删除堆中的项目。有什么作用swpIndx呢？（我需要知道做作业，我应该在其中编写删除堆中某个键的函数。）

4

1 回答 1

1

要从堆中删除一个键，我们可能希望在删除它之前将它与堆中的最后一个键交换，否则堆中会出现一个大洞。

但是，将最后一个节点与我们要删除的节点交换可能会打乱堆的顺序，这就是您提供的ReheapDown方法的用武之地。

我相信swpIndex参数是我们放置要删除的元素的索引。所以那部分代码基本上说：

if (there exists a left child) {
    if (there is no right child || left child < right child)
        minChild <- left child
    else
        minChild <- right child
}

我认为该参数是不必要的，因为它的唯一目的似乎是检查左右孩子的存在；这也可以通过将 leftChild 和 rightChild 索引与 numElements 进行比较来完成。

希望这可以帮助 ：）

于 2012-06-09T23:12:39.153 回答