roadrunner icon indicating copy to clipboard operation
roadrunner copied to clipboard

[🧹 CHORE]: Update current `binary-heap` algorithm to `Fibonacci heap`

Open rustatian opened this issue 1 year ago • 2 comments

No duplicates 🥲.

  • [X] I have searched for a similar issue.

What should be improved or cleaned up?

Currently we have a priority queue for the JOBS plugin based on the custom binary-heap algorithm. We also have a few non-standard methods like exists or range remove in it. This algorithm was implemented as a starting point for our priority queue. Now it's time to improve it.

Here is a comparison table: image

This issue is to update our current implementation with the Fibonacci heap.

Some docs:

  1. https://www.cs.princeton.edu/~wayne/teaching/fibonacci-heap.pdf

Second option is to implement Strengthened Lazy Heaps algorithm.

rustatian avatar Jul 31 '23 08:07 rustatian

What about that issue?

Kaspiman avatar Jul 31 '23 18:07 Kaspiman

What about that issue?

Oh yeah, I forgot about that. Let's merge them into 1 ticket, thanks for pointing that out 👍🏻

rustatian avatar Jul 31 '23 19:07 rustatian