通过二叉树的数组表示的最小堆；Move多谢函数无限循环

Question

我正在使用一个数组数据结构实现一个最小堆，但是我的moveDown方法有一个问题(在根节点使用，如果根节点的子节点比它小，就将集合返回到一个堆)。我假设读者知道什么是min heap，但是我将描述它以防有人不知道或者我的理解不正确。

最小堆（在这种情况下）是由数组表示的二叉树，这样：

1. 根节点是数据结构中的最小值
2. 节点必须始终小于其子节点
3. 给定一个数组索引I的节点，它的左子节点位于索引I*21，右子节点位于I*22

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

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

但是每当我建议这种循环是个好主意时，我都会感到愤怒。上次有人建议这几乎是一种反模式，这是一种更礼貌的回答。