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

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:

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.

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.

3 Likes

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("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
B, 32
``````

Is it wrongly ordered?

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.

1 Like

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 đť“ž(đť‘›).

1 Like

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.