search

ignlg / heap-js

Efficient Binary heap (priority queue, binary tree) data structure for JavaScript / TypeScript. Includes JavaScript methods, Python's heapq module methods, and Java's PriorityQueue methods.
BSD 3-Clause "New" or "Revised" License
122 stars 8 forks source link

Issue popping when using custom comparator #31

Closed bjrnt closed 4 years ago

bjrnt commented 4 years ago

Hi,

Thanks for the library! I've had great use of it in a lot of online coding interviews. :)

Here's a quick reproduction of a bug I found when using custom comparators:

const heap = new Heap((a, b) => a[1] - b[1]);
heap.push([1, 2]);
heap.push([6, 0]);
heap.push([2, 3]);
heap.pop();
// => TypeError: Cannot read property '1' of undefined

After some digging, I found that inside getPotentialParent sometimes calls this.compare with an undefined value. Adding a quick typeof this.heapArray[j] !== "undefined" && to the function solves the issue but I am not sure if this is the best way to handle it. I'd be happy to send a PR with tests if you think this is a good solution to the problem.

ignlg commented 4 years ago

Hello @bjrnt, thanks for your feedback. I will try it within the next branch to be sure that it is not already fixed. Also I will add your example as a test :)

ignlg commented 4 years ago

It should be fixed now.

To allow undefined as a valid value inside the heap, it checks that the index is not beyond length before any comparison occurs.

I have added tests for custom heaps with custom comparators, and improved the existing ones.

@bjrnt Could you try the next branch and let me know if it fixed the issue for you?

Thanks :)

bjrnt commented 4 years ago

Yep, working great now! Thanks for the quick fix! :)