BinaryHeap example should show how to make a min-heap.

[forrestthewoods]

std::collections::BinaryHeap is a max-heap. A very common use case for users will be to make a min-heap. The basic example should include a min-heap.

[hellow554]

Do you think you would be able to make a PR based on e.g. https://stackoverflow.com/questions/54489368/how-do-i-create-a-binaryheap-that-pops-the-smallest-value-not-the-largest ?

[rasendubi]

Added an example in #60451

[HernandoR]

I would like to point out that the current tutorial of making min-heap introduces unnecessary Some(Reverse(v))) to the heap.

Is there any alternative I could approach to? or is it possible to introduce a compare function to binary heap?

[hellow554]

I would like to point out that the current tutorial of making min-heap introduces unnecessary Some(Reverse(v))) to the heap.

Not sure what you mean by unnecessary here. Can you explain?

Is there any alternative I could approach to? or is it possible to introduce a compare function to binary heap?

Using a newtype is the way to use a custom compare function. By using Reverse you simply reverse the original compare function which is most often easier than completely rewriting your own.

[HernandoR]

I would like to point out that the current tutorial of making min-heap introduces unnecessary Some(Reverse(v))) to the heap.

Not sure what you mean by unnecessary here. Can you explain?

As the tutorial shows, if I would like a min-heap based on binary heap, i need to unwrap the Reverse by

let Some(Reverse(n))=heap.pop() else {return ()};
// in compare with
let Some(n)=heap.pop() else {return ()};

It feels like an unnecessary gap for the differance of min or max heap. In my point of view, i would expect identical interface for the getter/setter since both are using the heap. How the heap is orderd should only be considered on the builder of that heap. i.e.

//not working, just to show the concept of decide the order at building a heap
let mut rev_heap = BinaryHeap::<Reverse>::new();

// user, setting
rev_heap.push(1);
rev_heap.push(5);
rev_heap.push(2);

// user, getting
// If we pop these scores now, they should come back in the reverse order.
assert_eq!(rev_heap.pop(), Some(1));
let Some(n)=rev_heap.pop() else {return ()};
assert_eq!(n,2);

To conclude, i think the general use case is to set the order when defining the heap, rather than when the first time using it.

ps. I could fully understand that we would like to provide a minimal and stable interface for such a basic data structure. And let people decide what they actually want. But we could discuss if there's a better way, couldn't we?

[hellow554]

Alright, I get your point. Let me try to clarify some things.

It seems to me that you're new to Rust. If you questions feel free to ask them on ULRO
That's the appropriate place, since this Tracker is used to track issues.

In my point of view, i would expect identical interface for the getter/setter since both are using the heap.

They are! Reverse has nothing to do with the heap. It's just a struct like Option or MyStruct. There's nothing special about it. Reverse just reversed the PartialOrd Trait, nothing more, nothing less

How the heap is orderd should only be considered on the builder of that heap

That's a possible approach, but not the one taken by the Rust language. Here the struct that is put in the Heap says how ordering should be done by using the PartialOrd / Ord Trait. This makes Things easier, because you dont have to store a closure in the heap struct.

let mut rev_heap = BinaryHeap::<Reverse>::new();

The correct one would be: BinaryHeap::<Reverse<i32>>::new();

To conclude, i think the general use case is to set the order when defining the heap, rather than when the first time using it.

That's not correct. As said, the struct inside the heap (in your case i32) defines the ordering. Not "the first time using it".

I hope this makes it clearer to you. If not, feel free to open a new topic on the users forum