Home > Blockchain >  Seg Fault with Binary Heap Class when running on Linux, Insert into Heap problems
Seg Fault with Binary Heap Class when running on Linux, Insert into Heap problems

Time:12-15

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.

  • Related