PriorityQueue that keeps items when iterating it about ext-ds HOT 5 CLOSED

Something like a BST, with an in-order traversal?

from ext-ds.

You could easily create something like this around a PriorityQueue, can't you? You can use an internal Sequence as a buffer.

from ext-ds.

Just coming back to this to clarify what I meant by using a sequence as a buffer. You can pop all the items in the queue into a sequence (tuple would be better in 2.0) as you process (for example emit events), then push them all back into the priority queue.

Would be best to push them back in from highest to lowest priority to reduce the number of swaps that the priority would need to do.

from ext-ds.

@rtheunissen It might make sense to allow constructing the PQ from an array. You can construct a heap in O(n) time, while pushing into a heap element-wise is O(n log n).

from ext-ds.

@nikic What would the structure of the array be? Pairs of value/priority? It also just occurred to me that in order for the intermediary to work we'd have to pop the priority along with the value, as the priority it was inserted with might not be known at the time.

A better strucuture for the suggested use case might just be a sequence then, that you sort in O(n log n) after registering the events, or insert into using a binary search, which I think would be an O(log n) insert but the buffer unshift would make it a worst case O(n log n).

🤔

from ext-ds.