Priority queue with stable ordering of equal elements

help
1

Is there any ready to use implementation of priority queue which keeps equal elements in order of adding?

I tried std::collections::BinaryHeap but it doesn't work as I expected: https://play.rust-lang.org/?gist=b5449ec2bef09bd9a981b0327ee4921c&version=stable
This code prints

Element: Some(High(1))
Element: Some(High(2))
Element: Some(Low(1))
Element: Some(Low(3))
Element: Some(Low(2))

but I need this:

Element: Some(High(1))
Element: Some(High(2))
Element: Some(Low(1))
Element: Some(Low(2))
Element: Some(Low(3))
1 Like
2

From your example it looks like you don't want preserved order of adding, but completely ordered taking into account the inner priority value?

You're getting mixed results, because you don't compare the numbers in your Ord impl:

match *self {
                WithPriority::Low(_) => Ordering::Less,
                WithPriority::High(_) => Ordering::Greater,
            }

Instead of _ you should read the value and compare it, too.

And to preserve adding order on top of that, you could insert (WithPriority, usize) to the heap, where the second number is an internal counter you increase every time you add an item.

3

In my example, u32 was added just to manually mark order of pushed values. For my real code I need something more complex: priority queue for items like

struct WithPriority<Priority: Ord, Item> {
    priority: Priority,
    item: Item,
}

where ordering makes sense only for priority value, but not for item itself. And I want to preserve order of adding for items with same priority.

I thought about just adding monotonically increasing counter into the WithPriority struct. But this does not seem to be the right solution because counter will eventually overflow.

4

You can use u64 counter and expect it won't overflow (at 1 billion ops per second it will last 5 centuries)

2 Likes