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

我正在尝试编写一个恢复堆属性的函数。但是我一直都表现不好。

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

}

最佳答案

问题是，如果在第一个leftSon块中选择change作为if，则不会将其与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 );
    }
}

关于c - 修复C中的堆属性数据结构，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/28787620/