# Priority queue with stable ordering of equal elements

**URL:** <https://users.rust-lang.org/t/priority-queue-with-stable-ordering-of-equal-elements/14418>\
**Category:** help\
**Created:** [December 14, 2017, 1:55pm UTC](https://users.rust-lang.org/t/priority-queue-with-stable-ordering-of-equal-elements/14418 "2017-12-14T13:55:20Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![im-0](https://avatars.discourse-cdn.com/v4/letter/i/d78d45/32.png) [@im-0](https://users.rust-lang.org/u/im-0)\
**Post date:** [December 14, 2017, 1:55pm UTC](https://users.rust-lang.org/t/priority-queue-with-stable-ordering-of-equal-elements/14418/1 "2017-12-14T13:55:20Z")

</div>

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](https://play.rust-lang.org/?gist=b5449ec2bef09bd9a981b0327ee4921c&version=stable)  
This code prints

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

```

but I need this:

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

```

---

<div class="post-metadata">

**Author:** ![kornel](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/kornel/32/4823_2.png) [@kornel](https://users.rust-lang.org/u/kornel)\
**Post date:** [December 14, 2017, 2:33pm UTC](https://users.rust-lang.org/t/priority-queue-with-stable-ordering-of-equal-elements/14418/2 "2017-12-14T14:33:35Z")

</div>

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:

```rust
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.

---

<div class="post-metadata">

**Author:** ![im-0](https://avatars.discourse-cdn.com/v4/letter/i/d78d45/32.png) [@im-0](https://users.rust-lang.org/u/im-0)\
**Post date:** [December 14, 2017, 4:19pm UTC](https://users.rust-lang.org/t/priority-queue-with-stable-ordering-of-equal-elements/14418/3 "2017-12-14T16:19:51Z")

</div>

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

```rust
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.

---

<div class="post-metadata">

**Author:** ![kornel](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/kornel/32/4823_2.png) [@kornel](https://users.rust-lang.org/u/kornel)\
**Post date:** [December 14, 2017, 5:09pm UTC](https://users.rust-lang.org/t/priority-queue-with-stable-ordering-of-equal-elements/14418/4 "2017-12-14T17:09:08Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![steffahn](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/steffahn/32/47569_2.png) [@steffahn](https://users.rust-lang.org/u/steffahn)\
**Post date:** [January 12, 2023, 8:46am UTC](https://users.rust-lang.org/t/priority-queue-with-stable-ordering-of-equal-elements/14418/5 "2023-01-12T08:46:42Z")

</div>

Closed on January 12, 2023, 8:46am UTC