C++用vector实现二叉堆调用removeMin删除元素后程序崩溃报错

核心错误点 #

• 你当前的removeMinJob实现完全不符合二叉堆的最小元素删除逻辑，是触发下标越界的根本原因：
  二叉堆删除最小元素的标准流程为O(logn)复杂度，你直接调用jobs.erase(jobs.begin())会触发两个问题：
  1. 该操作会将vector中所有剩余元素整体前移，时间复杂度退化到O(n)，完全不符合堆的设计性能要求
  2. 删除后你没有做任何堆性质维护操作，后续执行插入、打印、堆调整等逻辑时，原本基于堆父子节点下标规则（父节点i对应子节点2i+1/2i+2）的访问会直接越界，和你遇到的报错完全吻合
• 额外排查点：如果你调用removeMinJob后其他逻辑没有先调用isEmpty()判断就直接访问jobs[0]，当堆为空时也会触发同样的越界报错

修正方案 #

正确的removeMinJob实现逻辑如下：

Job Batch::removeMinJob() {
    if (isEmpty()) 
        throw std::runtime_error("No jobs are present."); // 建议替换原字符串抛出为标准异常，更易捕获处理
    
    Job minJob = jobs[0];
    // 将最后一个元素移到根节点位置
    jobs[0] = jobs.back();
    // 弹出最后一个元素，为O(1)操作，性能远高于erase首元素
    jobs.pop_back();
    // 对新的根节点执行下沉操作，维护小顶堆性质，需提前实现percolateDown逻辑
    if (!isEmpty()) {
        percolateDown(0);
    }
    return minJob;
}

你需要额外实现小顶堆的下沉调整函数，参考实现如下：

// 注意需提前重载Job类的<运算符，或替换为你自定义的Job优先级比较逻辑
void Batch::percolateDown(int index) {
    int childIndex;
    Job temp = jobs[index];
    int heapSize = jobs.size();
    for (; index * 2 + 1 < heapSize; index = childIndex) {
        childIndex = index * 2 + 1;
        // 找到两个子节点中优先级更高（值更小）的节点
        if (childIndex != heapSize - 1 && jobs[childIndex + 1] < jobs[childIndex]) {
            childIndex++;
        }
        if (jobs[childIndex] < temp) {
            jobs[index] = jobs[childIndex];
        } else {
            break;
        }
    }
    jobs[index] = temp;
}

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