Is `std::collections::binary_heap` stable (as in `stable_sort`)?

help
1

The priority_queue in C++ is not stable, i.e. if two elements a and b are equal, then they may not come out of the heap in their insertion order. More here Stable Priority Queues? – Daniel Lemire's blog.

I need this property. I wrote a few tests, and it looks like that std::collections::binary_heap is stable, but I can't be sure since it could be just a happy accident. docs don't mention the FIFO/stable property.

As mentioned in the blog I linked in the first paragraph, there seems to be a simple solution. I can add count field to my struct and use it in deriving Ord/PartialOrd trait.

Is there a crate you recommend that provides stable binary heaps if std::collections::binary_heap is not guaranteed to be stable?

2

Heapsort is not stable, so I'd be surprised if BinaryHeap was stable -- it probably can't be, because if it was then we could use it for an efficient in-place stable sort.

3 Likes
3

This demonstrates that BinaryHeap is definitely not stable:

use std::collections::BinaryHeap;
use std::cmp::{PartialEq,Eq,Ord,PartialOrd,Ordering};

#[derive(Copy,Clone,Debug)]
struct S(usize);

impl PartialEq for S {
    fn eq(&self, _:&Self) -> bool { true }
}

impl Eq for S {}

impl PartialOrd for S {
    fn partial_cmp(&self, _:&Self) -> Option<Ordering> { Some(Ordering::Equal) }
}

impl Ord for S {
    fn cmp(&self, _:&Self) -> Ordering { Ordering::Equal }
}

fn main() {
    let mut heap:BinaryHeap<S> = (0..4).map(S).collect();
    
    let mut heap_order = vec![];
    while let Some(s) = heap.pop() {
        heap_order.push(s.0);
    }
    
    dbg!(heap_order);
}

Output:

[src/main.rs:30] heap_order = [
    0,
    2,
    1,
    3,
]
3 Likes
4

I don't know of a crate, but it's relatively easy to incorporate this trick into your own FifoHeap type:

use std::collections::BinaryHeap;

#[derive(Clone,Debug)]
pub struct FifoHeap<T> {
    seq: usize,
    heap: BinaryHeap<(T,usize)>
}

impl<T:Ord> FifoHeap<T> {
    pub fn new()->Self {
        FifoHeap {
            seq: usize::MAX,
            heap: BinaryHeap::new()
        }
    }
    
    pub fn push(&mut self, val:T) {
        let seq = self.seq.checked_sub(1).unwrap();
        self.seq = seq;
        self.heap.push((val, seq));
    }
    
    pub fn pop(&mut self)->Option<T> {
        let (val,_) = self.heap.pop()?;
        Some(val)
    }
}
2 Likes
5

I am doing the following self.heap.pop().map(|x| x.0). Will it be less efficient than the above?

6

It's just a stylistic choice; they should compile down to the same instructions.

1 Like
7

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.