C++实现vector堆化并统计值发生变化的元素位置数量问题

原有代码核心问题 #

• 参数职责冲突：diff同时承担下滤操作的当前节点索引、差异统计计数器两个完全无关的功能，是统计结果错误的直接原因。
• 堆化逻辑不完整：仅实现了单个节点的下滤操作，没有执行完整的建堆流程（遍历所有非叶子节点下滤），导致数组没有被完全堆化。
• 边界处理缺失：没有针对长度<=1的数组做特殊处理，会出现无意义的逻辑执行。

修复后的完整代码 #

#include <vector>
#include <iostream>
#include <algorithm>

// 辅助函数：单个节点下滤逻辑，仅负责堆调整，不涉及统计
void siftDown(std::vector<int>& v, int idx, int heapSize) {
    while (true) {
        int largest = idx;
        int left = 2 * idx + 1;
        int right = 2 * idx + 2;

        if (left < heapSize && v[left] > v[largest]) {
            largest = left;
        }
        if (right < heapSize && v[right] > v[largest]) {
            largest = right;
        }
        if (largest == idx) {
            break;
        }
        std::swap(v[idx], v[largest]);
        idx = largest;
    }
}

// 堆化+差异统计主函数
void heapifyAndCountDiff(std::vector<int>& v, int& diff) {
    diff = 0;
    int n = v.size();
    // 边界处理：单元素/空数组无变化直接返回
    if (n <= 1) {
        return;
    }
    // 保存原始数组副本用于后续比对
    std::vector<int> original = v;
    // 完整建堆流程：从最后一个非叶子节点倒序遍历到根节点，逐个下滤
    for (int i = n / 2 - 1; i >= 0; --i) {
        siftDown(v, i, n);
    }
    // 逐位比对统计差异，无漏计多计问题
    for (int i = 0; i < n; ++i) {
        if (v[i] != original[i]) {
            diff++;
        }
    }
}

int main()
{
    // 测试用例1：单元素
    std::vector<int> v1 = {5};
    int diff1 = 0;
    heapifyAndCountDiff(v1, diff1);
    std::cout << "单元素测试：不同位置数 " << diff1 << "，堆内容：";
    for(int i: v1) std::cout << i << " ";
    std::cout << std::endl;

    // 测试用例2：1-10升序排列
    std::vector<int> v2 = {1,2,3,4,5,6,7,8,9,10};
    int diff2 = 0;
    heapifyAndCountDiff(v2, diff2);
    std::cout << "1-10升序测试：不同位置数 " << diff2 << "，堆内容：";
    for(int i: v2) std::cout << i << " ";
    std::cout << std::endl;

    // 原示例测试用例
    std::vector<int> v3 = {20, 19, 100, 2};
    int diff3 = 0;
    heapifyAndCountDiff(v3, diff3);
    std::cout << "原示例测试：不同位置数 " << diff3 << "，堆内容：";
    for(int i: v3) std::cout << i << " ";
    std::cout << std::endl;

    return 0;
}

修复逻辑说明 #

• 完全拆分堆调整逻辑和统计逻辑，避免参数混用导致的统计错误
• 补充了标准的全量建堆流程，保证输出的数组是符合要求的大顶堆
• 通过原始数组副本比对的方式统计差异，不受堆调整过程的交换逻辑影响，统计结果100%准确
• 新增边界判断，单元素/空数组直接返回diff=0，符合预期

内容的提问来源于stack exchange，提问作者Byron