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

Question

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 outputs 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.

*runs 100% correct on OSX* -- Welcome to the world of C++, where undefined behavior could mean that the program seems to work. If instead of `typ *heap;` you had `std::vector heap;`, then you would see the failure, regardless of what compiler you used, if you had `heap.at(size) = k;` instead of `heap[size] = k;`. Yet again, another advantage of using a container that knows its size, and has the ability to do bounds checking, unlike raw pointers and `new[]`. — PaulMcKenzie, Dec 14 '21 at 21:08

Alan Birtles · Accepted Answer · 2021-12-14T21:06:06.050

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?

I have tried to update the insert function to what you have posted and it no longer crashes but the output is now incorrect. I figured it was something with insert and trying to resize the array when its full but I wasn't sure. In my implementation I define the Heap starting at index 1 and it contains items up to size instead of from 0 to size-1. I'll continue to mess with this function, thank you for all the information. — codermke, Dec 14 '21 at 21:49
I intend the insert function to add the new item at the end of the heap, then use the while loop to restore any heap property errors after the insert. On top of that, resizing the array to double the size when it is full. — codermke, Dec 14 '21 at 21:52

score 0 · Answer 2 · answered Dec 14 '21 at 22:40

0

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.

answered Dec 14 '21 at 22:40

codermke

3
2

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

2 Answers2