The priority_queue in C++ is not stable, i.e. if two elements a and b are equal, then they may not come out of the heap in their insertion order. More here Stable Priority Queues? – Daniel Lemire's blog.

I need this property. I wrote a few tests, and it looks like that std::collections::binary_heap is stable, but I can't be sure since it could be just a happy accident. docs don't mention the FIFO/stable property.

As mentioned in the blog I linked in the first paragraph, there seems to be a simple solution. I can add count field to my struct and use it in deriving Ord/PartialOrd trait.

Is there a crate you recommend that provides stable binary heaps if std::collections::binary_heap is not guaranteed to be stable?

Heapsort is not stable, so I'd be surprised if BinaryHeap was stable -- it probably can't be, because if it was then we could use it for an efficient in-place stable sort.