How will the items be sorted and popped, if their priority is equal? Is it insertion o

To clarify, is this test guaranteed to succeed? <div class="snippet-clipboard-cont

Yes. And also <div class="highlight highlight-source-rust notranslate position-rel

Documentation does not specify behavior for equal priorities about priority-queue HOT 3 CLOSED

garro95 commented on June 15, 2024

Documentation does not specify behavior for equal priorities

from priority-queue.

Comments (3)

garro95 commented on June 15, 2024 1

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.

from priority-queue.

MatejSloboda commented on June 15, 2024

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?

from priority-queue.

garro95 commented on June 15, 2024

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());
}