Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[Feature] Add PriorityQueue.fromList constructor #249

Open
webnickell opened this issue Oct 1, 2022 · 1 comment
Open

[Feature] Add PriorityQueue.fromList constructor #249

webnickell opened this issue Oct 1, 2022 · 1 comment

Comments

@webnickell
Copy link

There is no PriorityQueue.fromList constructor. So, you can actually create priority queue from existing list for O(log(n)). But in current implementation you can just add elements one by one. It gives us O(n*log(n)). Yes, we have addAll method, but in documentation you can see, that it's just repeat add method. So we need it to improve current realization.

@lrhn
Copy link
Member

lrhn commented Jun 13, 2023

Creating a priority queue from a list requires copying the list elements, unless it's allowed to work on the list itself. It's always dangerous to have a data structure on a shared backing store, but I guess you'd be opting in to that danger.

It also requires ensuring that the list is in priority queue order, which is more than O(log(N)). It, at least, has to look at each element once. Then it might need to move some, if they aren't in order.

I can see the possible benefit of being able to supply the backing store, possibly make the queue not able to grow (if backing store is fixed length), and maybe promising that the elements are already ordered correctly (which will be checked, but not fixed if not true).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants