c++ - 通过二叉树的数组表示的最小堆； MoveDown 函数无限循环

Question

我正致力于使用数组数据结构实现最小堆，但我的 moveDown 方法存在问题(如果根的子节点都小于它，则在根节点使用该方法将集合返回到堆)。我假设读者会知道什么是最小堆，但我会对其进行描述以防有人不知道或我的理解不正确。

最小堆(在本例中)是一个二叉树，由一个数组表示:

1. 根节点是数据结构中的最小值
2. 一个节点必须总是小于它的 child
3. 给定数组索引 I 的节点，它的左 child 索引为 I*2 + 1，右 child 索引为 I*2 + 2

我目前遇到的问题是我的 moveDown 函数在交换时进入无限循环。我很难找到逻辑错误，所以我担心它可能更接近根源(双关语，我情不自禁)。

heap.cpp 文件的重要数据成员:

int size;
MiniVector array;// The implementing custom array
void moveDown(int root);

我的 heap.cpp 文件中的 moveDown 函数:

void BinaryHeap::moveDown( int root ){

    int temp = root;
    int tempLC = temp*2 + 1;//LeftChild
    int tempRC = temp*2 + 2;//RightChild

    //Not a leaf
    while( ( tempLC < array.size() && tempRC < array.size() )
        &&
    ( (array[temp] > array[tempLC]) || (array[temp] > array[tempRC]) ) ){

        int hold = array[temp];

        if( array[temp] > array[tempRC] ){

            array[temp] = array[tempRC];
            array[tempRC] = hold;
            temp = tempRC;
        }

        else{

            array[temp] = array[tempLC];
            array[tempLC] = hold;
            temp = tempLC;
        }

        int tempLC = temp*2 + 1;//LeftChild
        int tempRC = temp*2 + 2;//RightChild
    }
}

Answer 1

您重新声明变量。在 while 循环的底部

    int tempLC = temp*2 + 1;//LeftChild
    int tempRC = temp*2 + 2;//RightChild

应该是

    tempLC = temp*2 + 1;//LeftChild
    tempRC = temp*2 + 2;//RightChild

不会发生在 Java 中。

如果您将循环重写为中间有中断的无限 for 循环，也不会发生这种情况

for (;;)
{
    int tempLC = temp*2 + 1;//LeftChild
    int tempRC = temp*2 + 2;//RightChild
    if (...)
        break;
    ...
}

但每当我提出这种循环是个好主意时，我都会被激怒。上次有人建议它“几乎是一种反模式”，这是比较礼貌的回应之一。