Reverse order Priority Queue

Question

Does anyone know if it is possible to reverse the order in a priority queue in Rust? When I peek the queue, I want the lowest i32 to be received. However, it seems that it by default returns the highest i32.

Edit

This is the package I am using: docs.rs/priority-queue/1.2.0/priority_queue

Hi @MaxTorreSchau, you should probably tell which package you are using. As I don't believe this is a native type in rust ? it is this one : https://docs.rs/priority-queue/1.2.0/priority_queue/ ? — Paulo, Sep 22 '21 at 11:32
Then maybe take a look at the double priority queue: https://docs.rs/priority-queue/1.2.0/priority_queue/double_priority_queue/struct.DoublePriorityQueue.html It seems the `peek_min` will be perfect for your need — Paulo, Sep 22 '21 at 11:33
If you don't need to change the order on the fly, another option is to inverse the priorities when pushing an item in the queue. I.e. `push (item, -prio)` instead of `push (item, prio)`. — Jmb, Sep 22 '21 at 11:49
Does this anwer your question? [How do I create a BinaryHeap that pops the smallest value, not the largest?](https://stackoverflow.com/questions/54489368/how-do-i-create-a-binaryheap-that-pops-the-smallest-value-not-the-largest) It's for a `BinaryHeap`, but the approach works for any data structure that relies on `PartialEq`. — Sven Marnach, Sep 22 '21 at 11:51

Solomon Ucko · Answer 1 · 2021-12-16T23:18:22.777

4

Unless you need to access it from both ends, using std::cmp::Reverse should be the most efficient solution. (e.g. PriorityQueue<i32, Reverse<i32>>, .push(x, Reverse(x)))

edited Dec 16 '21 at 23:18

answered Sep 22 '21 at 13:24

Solomon Ucko

5,724
3
24
45

How do you use it with the PriorityQueue? – Jean Dec 16 '21 at 19:35
@Jean Does my edit answer your question? – Solomon Ucko Dec 16 '21 at 23:18
Perfectly, thank you! – Jean Dec 16 '21 at 23:23
1

Actually, how do you access the Reverse value? Found it, it's a tuple, that's quite confusing. So `reverse_variable.0` gives the value. – Jean Dec 16 '21 at 23:32

score 0 · Accepted Answer · answered Sep 22 '21 at 11:43

As per the documentation of the crate (package).

I believe you should be using DoublePriorityQueue instead of PriorityQueue as it offers to peek in the queue the highest value or the lowest. Using peek_max or peek_min respectively.

See the snippet of code they provide in the documentation:

use priority_queue::DoublePriorityQueue;

let mut pq = DoublePriorityQueue::new();

assert!(pq.is_empty());
pq.push("Apples", 5);
pq.push("Bananas", 8);
pq.push("Strawberries", 23);

assert_eq!(pq.peek_max(), Some((&"Strawberries", &23)));
assert_eq!(pq.peek_min(), Some((&"Apples", &5)));

pq.change_priority("Bananas", 25);
assert_eq!(pq.peek_max(), Some((&"Bananas", &25)));

for (item, _) in pq.into_sorted_iter() {
    println!("{}", item);
}

Reverse order Priority Queue

2 Answers2