'priq' (no pun intended?) Priority Queue with partial ordering of scores

[bexxmodd]

Long story short, I learned that std::BinaryHeap only allows elements with the Ord trait which prevents us from using floating points as scores.

So, I implemented a priority queue that allows PartialOrd by placing NAN values at the end of the queue, with better performance than the std version (for some instances) and some extra functionality:

Github | crates.io | Documentation

I got a lot of good feedback when I shared the v0.1.0 version on Reddit and I'm hoping to hear some advice/feedback/roasting for v0.2.0 as well as it helps me to learn and makes my projects well-tailored and useful to the community.

[alice]

I mean, this probably works fine for NaN, but I very strongly doubt that it would work for other partially ordered types. A partial order can be weird in other ways than just having elements that are not comparable — for example if you said that one string was smaller than another if the latter string starts with the former. Then a < ab and a < ac but you don't have ab < ac, nor do you have ac < ab.

It seems like the proper solution to this is to pick a wrapper around f32 that equips it with a total order, which there are already several crates out there that can do.

[bexxmodd]

I don't quite understand why there will be no ab < ac and what does it change?

I ran this test:

    let mut pq = PriorityQueue::<String, usize>::new();
    pq.put("AB".to_string(), 22);
    pq.put("AD".to_string(), 93);
    pq.put("A".to_string(), 14);
    pq.put("AC".to_string(), 52);
    pq.put("B".to_string(), 32);

    pq.into_sorted_vec().into_iter().for_each(
        |(s, e)| println!("{}, {}", s, e)
    );

and got this order:

A, 14
AB, 22
AC, 52
AD, 93
B, 32

Is it wrongly ordered?

[alice]

You're using the normal ordering of strings, which is a total order. I proposed a different ordering, which is only partial. My ordering is that s1 ≤ s2 if and only if s2 starts with s1. This is a valid partial ordering, but it is not total.

[steffahn]

Considering re-allocations from re-sizing, your claimed “worst case” time complexity seems off. That ought to mention amortization. It’s not actually the “worst case” time; worst case would be 𝓞(𝑛).