Documentation does not specify behavior for equal priorities

[MatejSloboda]

How will the items be sorted and popped, if their priority is equal? Is it insertion order? Is it arbitrary order? Is the order deterministic/repeatable? Does it depend on hasher? It would be nice if the documentation specified what minimum guarantee I can assume. At the moment I must assume the worst case scenario of completely random order, since the documentation doesn't indicate otherwise.

[garro95]

The order is arbitrary but deterministic, in the sense that you can repeat the exact same experiment with the same results, but equal element inserted in a certain order can be extracted in reverse order. It does not depend on the hasher, but only on the heap algorithm.

I will properly update the documentation with this information. Thank you.

[MatejSloboda]

To clarify, is this test guaranteed to succeed?

let mut a = PriorityQueue::new();
let mut b = PriorityQueue::new();

a.push("Apples", 1);
b.push("Apples", 1);
a.push("Oranges", 1);
b.push("Oranges", 1);
a.push("Pears", 2);
b.push("Pears", 2);
a.push("Lemons", 1);
b.push("Lemons", 1);

// note, we don't care if "Apples" get popped before "Oranges"
// we only care that queues 'a' and 'b' will pop them in the same (arbitrary) order 
// if we performed the same operations in the same order on queues 'a' and 'b'
assert_eq!(a.pop(), b.pop());
assert_eq!(a.pop(), b.pop());
assert_eq!(a.pop(), b.pop());
assert_eq!(a.pop(), b.pop());

In other words, if I have two queues and apply the same operations in the same order, are they guaranteed to remain synchronized?

[garro95]

Yes. And also

use priority_queue::PriorityQueue;
use hashbrown::hash_map::DefaultHashBuilder;

fn main() {
    let mut a = PriorityQueue::new();
    let mut b = PriorityQueue::<_, _, DefaultHashBuilder>::with_default_hasher();

    a.push("Apples", 1);
    b.push("Apples", 1);
    a.push("Oranges", 1);
    b.push("Oranges", 1);
    a.push("Pears", 2);
    b.push("Pears", 2);
    a.push("Lemons", 1);
    b.push("Lemons", 1);

    // note, we don't care if "Apples" get popped before "Oranges"
    // we only care that queues 'a' and 'b' will pop them in the same (arbitrary) order 
    // if we performed the same operations in the same order on queues 'a' and 'b'
    assert_eq!(a.pop(), b.pop());
    assert_eq!(a.pop(), b.pop());
    assert_eq!(a.pop(), b.pop());
    assert_eq!(a.pop(), b.pop());
}

does not fail