search

AngelicosPhosphoros / keyed_priority_queue

MIT License
27 stars 5 forks source link

Weak heap based priority queue? #11

Open eaglgenes101 opened 3 years ago

eaglgenes101 commented 3 years ago

Weak heaps have more favorable time complexities than binary heaps and do fewer comparisons than them.

I modified my own copy of this crate to be able to use a weak heap as a backend instead of a binary heap, and benchmarking seems to show that they do live up to the theory. However, weak heaps have more overhead than binary heaps, so binary heaps will still be preferred in some applications.

Would this be an addition to this crate you would be willing to accept, and if so, how should I integrate it with the rest of the crate?

AngelicosPhosphoros commented 3 years ago

@eaglgenes101 Hi, thank for information!

Can you send me link to your modification? I am currently without internet but I would be able to look into in next week.

eaglgenes101 commented 3 years ago

https://github.com/eaglgenes101/keyed_priority_queue

Do note, however, that these changes were made largely for exploration purposes, and IMO are not suited for merging yet. We can probably think of a better API design than what I threw together...