dart-lang / core

This repository is home to core Dart packages.
https://pub.dev/publishers/dart.dev
BSD 3-Clause "New" or "Revised" License
15 stars 4 forks source link

[Feature] Add PriorityQueue.fromList constructor #638

Open webnickell opened 2 years ago

webnickell commented 2 years ago

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 commented 1 year ago

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).