search

robinmessage / fibonacci

A simple C++ fibonacci heap implementation
32 stars 17 forks source link

Segfault when decreasing key #3

Closed NTUwanderer closed 6 years ago

NTUwanderer commented 6 years ago

void test2() { using namespace std; FibonacciHeap h; node* nodes = new node[9]; nodes[0] = h.insert(0); nodes[1] = h.insert(4); nodes[7] = h.insert(8); nodes[2] = h.insert(12); nodes[6] = h.insert(9); nodes[8] = h.insert(15); nodes[5] = h.insert(11); nodes[3] = h.insert(25); h.decreaseKey(nodes[3], 19); h.decreaseKey(nodes[8], 14); delete[] nodes; }

With the use case above, I get a segfault when decreasingKey of node[8]. Please check. Thanks!

robinmessage commented 6 years ago

Thanks for the bug. How did you generate this test case? I'll check it out.

NTUwanderer commented 6 years ago

I tried to implement the dijkstra's shortest path, and use the graph: https://www.geeksforgeeks.org/greedy-algorithms-set-6-dijkstras-shortest-path-algorithm/ as the test case. The full test procedure is as below.

void test2() { using namespace std; FibonacciHeap h; node* nodes = new node[9]; nodes[0] = h.insert(0); h.removeMinimum(); nodes[1] = h.insert(4); nodes[7] = h.insert(8); h.removeMinimum(); nodes[2] = h.insert(12); h.removeMinimum(); nodes[6] = h.insert(9); nodes[8] = h.insert(15); h.removeMinimum(); nodes[5] = h.insert(11); h.removeMinimum(); nodes[3] = h.insert(25); h.removeMinimum(); h.decreaseKey(nodes[3], 19); h.decreaseKey(nodes[8], 14); delete[] nodes; }

robinmessage commented 6 years ago

Hi, I've fixed this bug now. Please note, this library lacks an extensive test suite so might not be perfect for production use (as you've noticed!). If I have time, I will add some more testing. Thanks for reporting and I hope it is useful.