代码之家 › 专栏 › 技术社区 › Arda Ä°brahim Gökçe

在遍历最小堆时获取垃圾值

min-heap traversal heap c++

-1

Arda Ä°brahim Gökçe · 技术社区 · 8 年前

这是我的遍历方法:

void heapTraversal(){
        for(int i = 0; i<maxsize; i++){
            cout << "Current value is : " << hipa[i] << endl;
            if(hipa[(2*i)+1]){
                cout << "Left child is : " << hipa[(2*i)+1] << endl;
            }
            else{
                cout << "Left child does not exist" << endl;
            }
            if(hipa[(2*i)+2]){
                cout << "Right child is : " << hipa[(2*i)+2] << endl;
            }
            else{
                cout << "Right child does not exist" << endl;
            }

这是我的输出:

Current value is : 7
Left child is : 9
Right child is : 17
Current value is : 9
Left child is : 15
Right child is : 12
Current value is : 17
Left child is : 25
Right child is : 22
Current value is : 15
Left child is : 1769234787
Right child does not exist
Current value is : 12
Left child does not exist
Right child does not exist
Current value is : 25
Left child does not exist
Right child is : 1852112910
Current value is : 22
Left child is : 1395618676
Right child is : 1701994856

它似乎工作正常,但我有所有这些垃圾值,我不应该有,我无法确定问题。

我怀疑控制结构有问题,我的逻辑正确吗,还是应该使用其他if语句?

2 回复 | 直到 8 年前

Jim Mischel 8 年前

即使你在回答中发布了“修复”,你也会遇到同样的问题 heap_size >= (maxsize/2) 。您必须检查计算的左、右子索引。更正的代码:

void heapTraversal(){
    for(int i = 0; i<heap_size; i++){
        cout << "Current value is : " << hipa[i] << endl;
        int left = (2*i)+1;

        if(left < heap_size && hipa[left]){
            cout << "Left child is : " << hipa[left] << endl;
        }
        else{
            cout << "Left child does not exist" << endl;
        }

        int right = left+1;
        if(right < heap_size && hipa[right]){
            cout << "Right child is : " << hipa[right] << endl;
        }
        else{
            cout << "Right child does not exist" << endl;
        }

Arda Ä°brahim Gökçe 8 年前

我已经通过将for循环参数从maxsize更改为heap\u size解决了这个问题。 maxsize应该是堆的容量,而heap\u size是堆的当前大小。我为好奇者添加了类声明的其余部分。

class minHeap{
    int *hipa;
    int maxsize;
    int heap_size;

public:
    minHeap(int size);
    void minHeapbuild(int );

    int root(int i){
        return (i-1)/2;
    }
    int left(int i){
        return (2*i+1);
    }
    int right(int i){
        return (2*i+2);
    }

    int extractRoot();
    void decreaseKey(int i, int newKey);
    void deleteKey(int key);
    void addKey(int key);

    int getRoot(){
        return hipa[0];
    }
}