0

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

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

  1. 根节点是数据结构中的最小值
  2. 节点必须始终小于其子节点
  3. 给定一个数组索引为 I 的节点，它的左孩子将在索引 I*2 + 1 处，右孩子将在 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
    }
}
4

1 回答 1

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

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

于 2013-04-08T20:54:06.907 回答