search

lemire / FastPriorityQueue.js

a fast heap-based priority queue in JavaScript
Apache License 2.0
357 stars 57 forks source link

K smallest elements #14

Closed Kaisle closed 6 years ago

Kaisle commented 6 years ago

Thanks for an awesome implementation that outshines its competitors.

Would it be possible to add an O(k) or O(klogk) algorithm for finding the k smallest elements of the queue?

It can be done in O(klogn) time right now by polling k times and then adding them all back.

An O(k) or O(klogk) algorithm is possible, however, as described here: https://stackoverflow.com/questions/47892037/finding-k-smallest-elements-in-a-min-heap-worst-case-complexity

Do you believe it would possible to implement? I'm likely gonna take a crack at it myself.

lemire commented 6 years ago

Nice idea. PR invited.

Kaisle commented 6 years ago

Submitted a PR. Let me know what you think.

lemire commented 6 years ago

It is quite nice and I think that your PR captures the idea nicely. I have some nitpicking to do on the implementation as it feels it could be simpler/faster. See my comment.

lemire commented 6 years ago

https://github.com/lemire/FastPriorityQueue.js/commit/17f99575786ee79f68f8a6d08b5701475c61a59b

lemire commented 6 years ago

You are credited in the CONTRIBUTORS file.

Kaisle commented 6 years ago

Thank you @lemire. Nice work merging and love your improved implementation.

I would have updated the PR but was busy with exams so never got around to it.