Seg Fault with Binary Heap Class when running on Linux, Insert into Heap problems-CodePudding

I have implemented a binary heap class in C for school. I am having trouble with the program running on the school Linux server. My code runs 100% correctly on my Mac. It appears to SegFault after the first line of code is printed from the main.cpp. I have tried using GDB and haven't been able to pin point the issue. Running GDB gives me the following issue: Program received signal SIGSEGV, Segmentation fault. 0x00007ffff7ae8d68 in std::string::assign(std::string const&). Any help trying to correct this would be truly appreciated.

EDIT: I figured out it was the insert function causing the issues: I have updated the function to this:

UPDATED Insert Function:

template <class typ>
void Heap<typ>::insert(typ k) {
    if (size == 0) {
        size = size   1;
        heap[size] = k;
        return;
    }
    if (size == cap-1) {
        cap = cap * 2;
        typ *tempHeap = new typ [cap];
        for (int i = 1; i <= size; i  )
            tempHeap[i] = heap[i];
        delete [] heap;
        heap = tempHeap;
    }
    size = size   1;
    heap[size] = k; // insert item at end of heap
    int i = size; // set i to size
    while (i != 1 && heap[parent(i)] > heap[i]) { // move up to parents until heap property is restored all the way to the root
        swapKeys(&heap[parent(i)], &heap[i]); // swap items
        i = parent(i); // set i to parent of i
    }
}

This fixes the segfault that was happening and correctly outputs the heap.

CodePudding user response：

When inserting your first element you change cap from 0 to cap * 2, this is still 0 causing the subsequent heap[size] = k to have undefined behaviour. You should also presumably at this point also update cap to the new size of your array.

Your next bug is that you do:

size = size   1; // update size
heap[size] = k; // insert item at end of heap

Before this size could be equal to cap - 1, after incrementing it size then becomes cap causing heap[size] to have undefined behaviour.

The comment on this line doesn't match the code suggesting another bug?

int i = size; // set i to one less than size

I'm not sure of the intended behaviour of your program but the following code at least doesn't crash any more:

template <class typ>
void Heap<typ>::insert(typ k) {
    if (size == cap) { //resize the array when full
        cap = cap == 0 ? 2 : cap * 2;
        typ* tempHeap = new typ[cap];
        for (int i = 0; i < size; i  )
            tempHeap[i] = heap[i];
        delete[] heap;
        heap = tempHeap;
    }
    heap[size] = k; // insert item at end of heap
    int i = size; // set i to one less than size
    size = size   1; // update size
    while (i != 1 && heap[parent(i)] > heap[i]) { // move up to parents until heap property is restored all the way to the root
        swapKeys(&heap[parent(i)], &heap[i]); // swap items
        i = parent(i); // set i to parent of i
    }
}

On an unrelated note avoid #includeing cpp files, only header files should be included. Even if you rename Heap.cpp to Heap.h then you should also remove using namespace std;, this can lead to hard to track down compiler errors, see Why is "using namespace std;" considered bad practice?

CodePudding user response：

The issues with the program were related to resizing the heap when inserting and extracting values. Program was fixed after updating the insert and extractMin functions.