我的 C++ 堆实现有什么问题？

Question

我正在尝试为在线法官实现一个堆结构。实现很满意，我所有的测试用例都通过了，但是在线评委拒绝了。

insert 函数追加新元素，然后将其冒泡到二叉树中。 removeMax 函数用向量中的最后一个元素替换最大的元素，然后将其冒泡。

vector<int> heap;

int getMax(){
    return heap[0];
}

int getSize(){
    return heap.size();
}

void insert(int element){
    heap.push_back(element);
    int i = heap.size() - 1;

    while(element > heap[i / 2]) {
        swap(heap[i], heap[i / 2]);
        i = i / 2;
    }
}

void removeMax(){
    heap[0] = heap[heap.size() - 1];
    heap.pop_back();
    int i = 0;
    int iGreater = heap[i * 2] > heap[i * 2 + 1] ? i * 2 : i * 2 + 1;

    while(i < heap.size() &&  heap[i] < heap[iGreater]) {
        swap(heap[i], heap[iGreater]);
        i = iGreater;
        iGreater = heap[i * 2] > heap[i * 2 + 1] ? i * 2 : i * 2 + 1;
    }
}

Answer 1

您正在使用堆方程式：

节点 i 的父节点是节点 i/2
节点 i 的子节点是节点 2*i 和 2*i + 1

仅当您使用基于 1 的数组索引时才有效（索引 1 是数组的第一个元素）

但是 C++ 对向量（和数组）使用基于 0 的索引，所以这不起作用。你需要

节点 i 的父节点是节点 (i-1)/2
节点 i 的子节点是节点 2*i + 1 和 2*i + 2

你的 removeMax 结束条件也是错误的，导致你运行离开向量的末尾并得到未定义的行为。

Answer 2

几个问题：

在zero-indexed 向量中，索引i 处节点的children 位于i * 2 + 1 和i * 2 + 2。索引 i 处节点的 parent 位于 (i - 1) / 2
insert函数中的while循环到达根节点时必须退出，因为根没有parent。所以 i > 0 也应该是一个循环条件。
removeMax 应首先确保堆不为空，否则 heap[heap.size() - 1] 将有未定义的行为。
在赋值给iGreater之前首先要确保当前节点有children，否则像heap[i * 2 + 1]这样的表达式会有未定义的行为。也应该预见到一个节点只有一个 child 的情况。

这里更正：

void insert(int element){
    heap.push_back(element);
    int i = heap.size() - 1;

    while (i > 0 && element > heap[(i - 1) / 2]) {
        swap(heap[i], heap[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}

void removeMax(){
    if (heap.size() == 0) {
        return;
    }
    heap[0] = heap[heap.size() - 1];
    heap.pop_back();
    int i = 0;

    while (i * 2 + 1 < heap.size()) {
        int iGreater = i * 2 + 1;
        if (iGreater + 1 < heap.size() && heap[iGreater + 1] > heap[iGreater]) {
            iGreater++;
        }
        if (heap[i] >= heap[iGreater]) {
            break;
        }
        swap(heap[i], heap[iGreater]);
        i = iGreater;
    }
}

我的 C++ 堆实现有什么问题？

What is wrong with my C++ heap implementation?

c++

heap

binary-tree