c - 修复 C 中的堆属性数据结构

Question

我正在尝试编写一个恢复堆属性的函数。但我总是得到不好的结果。

void fixHeap(int heapSize, struct Edge* edgeArray, int i){//edgeArray is our heap-array.
    int leftSon = leftSonIndex(i);
    int rightSon = rightSonIndex(i);
    int change;
    if((leftSon <= heapSize) && (edgeArray[i].cost < edgeArray[leftSon].cost)){
        change = leftSon;
    }else{
        change = i;
        if((rightSon <= heapSize) && (edgeArray[change].cost < edgeArray[rightSon].cost)){
            change = rightSon;
        }
    }

    if(change != i){
        swap(edgeArray, i, change);
        i = change;

        fixHeap(heapSize, edgeArray, i);
    }

}

Answer 1

问题是，如果您选择 leftSon 作为第一个 if block 中的 change，那么您不会将其与rightSon 检查 rightSon > leftSon。
因此，在这种情况下，您的示例将失败 -:

  5
 / \
6   7  

事情应该是这样的-:

void fixHeap( int heapSize, struct Edge* edgeArray, int i ) //edgeArray is our heap-array.
{
    int leftSon = leftSonIndex( i );
    int rightSon = rightSonIndex( i );
    int change = i;

    if ( ( leftSon <= heapSize ) && ( edgeArray[change].cost < edgeArray[leftSon].cost ) )
    {
        change = leftSon;
    }
    if ( ( rightSon <= heapSize ) && ( edgeArray[change].cost < edgeArray[rightSon].cost ) )
    {
        change = rightSon;
    }
    if ( change != i )
    {
        swap( edgeArray, i, change );
        fixHeap( heapSize, edgeArray, change );
    }
}