Repository navigation
Add Min-Max Heap to std::collections #76250
Description
I just read a blog post about the Min-Max heap being faster than the Binary Heap on modern processors, while being strictly more powerful since you can pop from both ends: https://probablydance.com/2020/08/31/on-modern-hardware-the-min-max-heap-beats-a-binary-heap/
Given these benefits, and since BinaryHeap is included in std::collections, I wonder if it would make sense to include a MinMaxHeap as well?
Reacted by Sebastian Dröge, Eric Shimizu Karbstein, Svetlin Zarev, MarkTanashchuk, Suclogger, tofutofu, Tushar, João Marcos and Ryan Avella
Reacted by João Marcos
Activity
jonas-schievink commentedon Sep 2, 2020
This can be written as an external crate, has that been done already?
jonas-schievink commentedon Sep 2, 2020
Also, if this really ends up being a more powerful and faster
BinaryHeap, but with the same requirements on the user, thenBinaryHeapcan just be changed to a Min-Max heap internally. No new API needed.calebsander commentedon Sep 2, 2020
https://crates.io/crates/min-max-heap seems to be an existing implementation
scottmcm commentedon Sep 2, 2020
Hmm, can it? I thought that
Vec::from(BinaryHeap::from(vec))was defined to return the items in binary heap order, on which someone could potentially be depending. As you've said before, though, it sure would be nice to have.into_iter()be both sorted and double-ended for heaps...matklad commentedon Sep 2, 2020
I wonder if it's possible to do better than min-max heap by forgoing min-max property? Ie, an array can pack three interleaving tetrary max heaps.This give you the same parallel comparisons + four consequtive chilren in a row property.
EDIT: very quick&dirty benchmark did not disprove hypothesis that just making the heap four way makes it faster: https://github.com/matklad/quadheap/blob/91eb33870fc49280dda1e9be1fa904fc93d7364c/src/quad_heap.rs
EDIT EDIT: this is stupid and overly complicated. We can pack just one tetray heap into the array (i -> 4i + 1, 4i + 2, 4i + 3, 4i + 4) and that should be the best impl.
SkiFire13 commentedon Sep 3, 2020
The current comment for
BinaryHeap::into_vecsays that it "returns the underlying vector in arbitrary order", while theimpl<T> From<BinaryHeap<T>> for Vec<T>just states "Performs the conversion" so I guess it shouldn't be considered a breaking change,@matklad if you want to benchmark that you should probably remove those bound checks.
We should also consider removing branches from
sift_down_rangeandsift_down_to_bottom. In particular thehole.get(child) <= hole.get(right)condition can be treated arithmetically and theright < endcondition can be removed if the length is odd.This applies to both the current implementation and @matklad's quadheap.
scottmcm commentedon Oct 14, 2020
After the conversation about trying to stabilize
BinaryHeap::into_iter_sortedended up making me unhappy with the state of things there (#76234 (comment)), I'm personally more interested that I was previously in seeing this happen.Having such a heap would address a bunch of things:
BinaryHeap<Reverse<T>>works great, there's something really nice about just having.pop_min()and.pop_max()for clarity..into_iter()for ascending,.into_iter().rev()for descending. (There'd still beVec::from(...)or maybe some sort of.buffer_unordered() -> &[T]if people want to do something that doesn't care about the ordering.)In a way it'd be like the
VecDeque-vs-Vecpair.Dylan-DPC commentedon Jan 4, 2024
Closing this as it is better for this to be in a crate