遍历最小堆（min-heap）时出现垃圾值的技术排查求助

嘿，我一眼就看出你这遍历代码里的问题啦——这是新手写堆操作时很容易踩的两个小坑，咱们一步步来解决：

问题根源分析 #

1. 遍历范围错误：你用了maxsize作为循环的上限，但maxsize是堆数组的总容量，不是当前堆里实际存储的有效元素数量！数组里超出实际元素的位置都是未初始化的内存，读这些位置自然会得到垃圾值。
2. 子节点存在性判断错误：你用if(hipa[(2*i)+1])来判断左孩子是否存在，这是在检查元素值是否非零，但堆里完全可能包含0或者负数元素，而且就算这个位置有值，也可能已经超出了堆的有效元素范围，本质还是访问了无效内存。

修正后的代码 #

首先，你需要给堆类加一个size成员变量（或者在函数里能拿到当前堆的实际元素数），用来记录堆里到底有多少个有效元素。然后修改遍历函数：

void heapTraversal() { 
    // 用实际有效元素数size代替maxsize，只遍历堆里的有效节点
    for(int i = 0; i < size; i++) { 
        cout << "Current value is : " << hipa[i] << endl; 
        
        int leftChildIdx = 2 * i + 1;
        // 通过索引是否小于size来判断左孩子是否存在
        if(leftChildIdx < size) { 
            cout << "Left child is : " << hipa[leftChildIdx] << endl; 
        } else { 
            cout << "Left child does not exist" << endl; 
        } 
        
        int rightChildIdx = 2 * i + 2;
        // 同理判断右孩子
        if(rightChildIdx < size) { 
            cout << "Right child is : " << hipa[rightChildIdx] << endl; 
        } else { 
            cout << "Right child does not exist" << endl; 
        }
    }
}

关键说明 #

• 用size控制遍历范围：堆是动态结构，插入元素时size加1，删除元素时size减1，这样遍历只会涉及到真正存了堆元素的位置，不会碰未初始化的内存。
• 用索引判断子节点：堆是完全二叉树，左孩子的索引公式是2*i+1，右孩子是2*i+2，只要这个索引小于当前的size，就说明这个子节点是有效的；反之则不存在，不管这个位置的数组值是什么。

这样修改后，你就不会再看到奇怪的垃圾值啦！

内容的提问来源于stack exchange，提问作者Arda İbrahim Gökçe