c++ - 收到 "vector subscript out of range"错误。不确定发生访问冲突的位置

Question

我正在为我的一门 CS 类(class)做作业。我的教授希望我们使用数组来实现某种数据结构。我一直在检查我的代码，看看我可能访问了 vector 范围之外的哪些地方，但我没有看到任何我认为错误的地方。

当我运行测试 .cpp 文件时，它在中断之前只提取了一项。

有人可以指出我的代码中任何明显的错误吗？

class minHeap {
private:
vector<int> nodes;
int current;

int parent(int i) {
    return (i-1)/2;
}

int leftChild(int i) {
    return 2*i+1;
}

int rightChild(int i) {
    return 2*i+2;
}

void bubbleUp(int i) {
    if(i > 0) {
        int p = parent(i);
        if(nodes[i] < nodes[p]) {
            swap(nodes[i], nodes[p]);
            bubbleUp(p);
        }
    }
}

void bubbleDown(int i) {
    if(i < current) {
        int a = leftChild(i);
        int b = rightChild(i);

        if(a <= current) {
            if(nodes[i] > nodes[a] || nodes[i] > nodes[b]) {
                if(nodes[a] < nodes[b]) {
                    swap(nodes[i], nodes[a]);
                    bubbleDown(a);
                }
                else {
                    swap(nodes[i], nodes[b]);
                    bubbleDown(b);
                }
            }
        }
    }
}

public:
minHeap() {
    current = -1;
}

void insert(int x) {
    current++;
    nodes.push_back(x);
    bubbleUp(current);
}

int extractMin() {
    int min = nodes[0];
    swap(nodes[0], nodes[current]);
    current--;
    nodes.pop_back();
    bubbleDown(0);
    return min;
}

bool empty() {
    if(current < 0)
        return true;
    return false;
}
};

Answer 1

更新代码

int parent(int i) {
    int res = (i-1)/2;
    if (!(res >= 0 && res <= current)) cout << "error: parent(" << i << ") out of index";
    return res;
}

int leftChild(int i) {
    int res = 2*i+1;
    if (!(res >= 0 && res <= current)) cout << "error: leftChild(" << i << ") out of index";
    return res;
}

int rightChild(int i) {
    int res = 2*i+2;
    if (!(res >= 0 && res <= current)) cout << "error: rightChild(" << i << ") out of index";
    return res;
}

你会看到

error: rightChild(0) out of index1

从大小为 3 的堆中提取 min 时，需要考虑右子索引

if(a > current) {}
else {
    if(nodes[i] > nodes[a] || nodes[i] > nodes[b]) {