search

jaspervdj / psqueues

Priority Search Queues in three different flavors for Haskell
https://hackage.haskell.org/package/psqueues
Other
64 stars 24 forks source link

Monoid instances #19

Open ocharles opened 7 years ago

ocharles commented 7 years ago

Is it possible to provide Monoid instances? The presence of toList and fromLists suggests there is at least a implementation, but there is presumably something more efficient.

jaspervdj commented 7 years ago

I'm not sure if there's an efficient merge / union implementation, but I'll look into it. The alternative would be to insert all elements from the smallest queue into the larger one, but that's also a bit tricky since we don't keep track of the size right now.

ocharles commented 7 years ago

Yea, I think the only heaps with a good merge operation are Fibonacci heaps, but I don't believe the heaps in psqueues are Fibonacci heaps. Alternatively, I think binomial heaps have fairly good merge properties.