Heap.pop()?

[ryan-williams]

Any reason that Heap.remove doesn't return the min element in addition to the new Heap, i.e. (Option[A], Heap[A])?

I'm new to this repo, but would have guessed that was the much more common operation.

Perhaps a new pop method would be the way to add it?

This is simple and I need it, so I'll PR it if it sounds good, thanks!

[johnynek]

heap.minimumOption.map { m => (m, heap.remove) } would do it.

It would be a nice PR.

[ryan-williams]

Thanks. Thinking out loud for a second because I may be confused about what I need.

My plan is to use Heap in a cats-effect Ref and have multiple workers concurrently pulling work-items off of it.

I thought calling minimumOption and remove in sequence would introduce a race condition, but I guess the idea is that doing them in a single call to Ref.modify guarantees that the Heap was not modified during the sequence of operations.

So that answers my initial question ("Any reason…"), but nevertheless we're saying that a pop helper that combines both would be nice.

Let me know if anything jumps out as wrong there? Thanks again.

[johnynek]

That sounds right to me. Modify is atomic.

[anicolaspp]

@ryan-williams the reason is that I didn't think about it in my original implementation. Initially, there was Stew and me, we didn't have a lot of visibility and we were trying to push the library out there, so we didn't have a lot of requirements, just trying to do something that could help others, and here we are...

[cb372]

This issue can be closed, right? It’s been implemented.

[johnynek]

done.

https://github.com/typelevel/cats-collections/blob/361e6b0c55a14969c8119934b60643bb30fc6f33/core/src/main/scala/cats/collections/Heap.scala#L150

https://github.com/typelevel/cats-collections/blob/361e6b0c55a14969c8119934b60643bb30fc6f33/core/src/main/scala/cats/collections/PairingHeap.scala#L176

https://github.com/typelevel/cats-collections/blob/361e6b0c55a14969c8119934b60643bb30fc6f33/core/src/main/scala/cats/collections/PartiallyOrderedSet.scala#L138