简单的堆程序 - 这个变量做什么

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做什么？（我需要知道做一个家庭作业，我应该写这个函数来删除堆中的某个键。）简单的堆程序 - 这个变量做什么

来源

2012-06-09 forthewinwin

它只在函数中使用过一次，试图弄清楚'if'在哪里使用... –

要从堆中移除一个键，我们可能想要将它与删除它之前最后一个键在堆中，否则堆中会出现一个空洞。

然而，交换与我们要删除会破坏堆排序，这就是你提供的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-09 23:12:39 Shiv16

简单的堆程序 - 这个变量做什么

回答

相关问题