Is BinaryHeap pop() deterministic?

TLDR: Can I rely on that pop() in BinaryHeap will always return the elements in insertion order if they have the same priority?

I've stumbled uppon A Polkadot Postmortem - 24.05.2021 where they relied on an implementation detail not really guaranteed in the docs.

from this PR

slice.binary_search_by() said "If there are multiple matches, then any one of the matches could be returned." , but the implementation isn't the same thing. Actually, it returns the last one if multiple matches found.

My case is that I have a BinaryHeap of Reverse<Duration> and if two durations are the same pop() will return them in insertion order, my code relies on that being true but nowhere on pop() or the definition of BinaryHeap confirms that, my only relief is in their examples there's a comment that confirms it.

// We can iterate over the items in the heap, although they are returned in
// a random order.
for x in &heap {
    println!("{}", x);
}
// If we instead pop these scores, they should come back in order.

My question is can I rely on that pop() will always return the elements in insertion order if they have the same priority? I mostly ask because of the recent incident and because this assumption is only in a comment on the example and not on the docs of the method or type itself.

I don't believe even the comment in the example means insertion order. The point of the comment is that pop() always retrieves the greatest element as specified by Ord; so this says nothing about insertion order.

If you want to rely on insertion order being preserved, maintain an ever-increasing counter, and store (T, u64) in the heap. Since tuples are ordered lexicographically, this will correctly break ties.

5 Likes

No.

4 Likes

To be clear, it is deterministic, but the order is very hard to predict.

2 Likes

If you want to rely on insertion order being preserved, maintain an ever-increasing counter, and store (T, u64) in the heap. Since tuples are ordered lexicographically, this will correctly break ties.

Where do you find the lexicograpically ordered info?

EDIT: Well just as I post this I found it, why does this happens so often?

The sequential nature of the tuple applies to its implementations of various traits. For example, in PartialOrd and Ord , the elements are compared sequentially until the first non-equal set is found.

No, for the same reason that heapsort isn't a stable sort.

2 Likes

It's conventional in most programming languages. Also, you can check the source of impl PartialOrd for (T1, T2).