I am trying to implement a heap structure for an online judge. I am very happy with the implementation, it stands all of my test cases, but the online judge rejects it.

The insert function appends the new element and then bubbles it up the binary tree. The removeMax function replaces the greatest element with the last in the vetor and then bubbles it down.

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;
    }
}

CodePudding user response：

You are using the heap equations:

• parent of node i is node i/2
• children of node i are nodes 2*i and 2*i 1

which only works if you use 1-based array indexing (index 1 is the first element of the array)

But C uses 0-based indexing for vectors (and arrays), so this doesn't work. You need

• parent of node i is node (i-1)/2
• children of node i are nodes 2*i 1 and 2*i 2

Your ending condition for removeMax is also wrong, causing you to run off the end of the vector and get undefined behavior.

CodePudding user response：

Several issues:

• In a zero-indexed vector, the children of the node at index i are at i * 2 1 and i * 2 2. The parent of a node at index i is at (i - 1) / 2

• The while loop in the insert function must exit when arriving at the root node, since the root has no parent. So i > 0 should be a loop condition as well.

• removeMax should first ensure that the heap is not empty, otherwise heap[heap.size() - 1] will have undefined behaviour.

• Before assigning to iGreater it should be first ensured that the current node has children, as otherwise an expression like heap[i * 2 1] will have undefined behaviour. Also the case of a node with just one child should be foreseen.

Here is a correction:

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;
    }
}