# Why not use d-ary heap inside rather than binary heap **URL:** \ **Category:** libs\ **Created:** [April 30, 2023, 6:11am UTC](https://internals.rust-lang.org/t/why-not-use-d-ary-heap-inside-rather-than-binary-heap/18765 "2023-04-30T06:11:19Z")\ **Posts on this page:** 13\ **Page:** 1
**Author:** ![QuarticCat](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/quarticcat/32/10827_2.png) [@QuarticCat](https://internals.rust-lang.org/u/QuarticCat)\ **Post date:** [April 30, 2023, 6:11am UTC](https://internals.rust-lang.org/t/why-not-use-d-ary-heap-inside-rather-than-binary-heap/18765/1 "2023-04-30T06:11:19Z")
According to some experiments, d-ary heap (d\>2, typically d=4) generally performs better than binary heap. - [GitHub - hanmertens/dary\_heap: A d-ary heap in Rust](https://github.com/hanmertens/dary_heap) - [GitHub - skarupke/heap: Looking into the performance of heaps, starting with the Min-Max Heap](https://github.com/skarupke/heap) They have the same compact memory layout as binary heap. I don't see any drawback compared to binary heap. Plus, Rust has already chosen b-tree over red black tree for better cache performance. It's not weird to make the same decision once again. ---
**Author:** ![jhpratt](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/jhpratt/32/11640_2.png) [@jhpratt](https://internals.rust-lang.org/u/jhpratt)\ **Post date:** [April 30, 2023, 6:18am UTC](https://internals.rust-lang.org/t/why-not-use-d-ary-heap-inside-rather-than-binary-heap/18765/2 "2023-04-30T06:18:46Z")
Where do you believe a binary heap is being used? ---
**Author:** ![QuarticCat](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/quarticcat/32/10827_2.png) [@QuarticCat](https://internals.rust-lang.org/u/QuarticCat)\ **Post date:** [April 30, 2023, 6:19am UTC](https://internals.rust-lang.org/t/why-not-use-d-ary-heap-inside-rather-than-binary-heap/18765/3 "2023-04-30T06:19:54Z")
I mean `std::collections::BinaryHeap`. Sorry for ambiguity. ---
**Author:** ![jhpratt](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/jhpratt/32/11640_2.png) [@jhpratt](https://internals.rust-lang.org/u/jhpratt)\ **Post date:** [April 30, 2023, 6:23am UTC](https://internals.rust-lang.org/t/why-not-use-d-ary-heap-inside-rather-than-binary-heap/18765/4 "2023-04-30T06:23:23Z")
Honestly, I didn't even know it existed, and I know the standard library quite well. ---
**Author:** ![scottmcm](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/scottmcm/32/2355_2.png) [@scottmcm](https://internals.rust-lang.org/u/scottmcm)\ **Post date:** [April 30, 2023, 8:30am UTC](https://internals.rust-lang.org/t/why-not-use-d-ary-heap-inside-rather-than-binary-heap/18765/5 "2023-04-30T08:30:58Z")
Sounds like you'd be interested in > > > 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\`\](https://doc.rust-lang.org/std/collections/struct.BinaryHeap.html) is included in \`std::collections\`, I wonder if it would make sense to include a \`MinMaxHeap\` as well? ---
**Author:** ![QuarticCat](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/quarticcat/32/10827_2.png) [@QuarticCat](https://internals.rust-lang.org/u/QuarticCat)\ **Post date:** [April 30, 2023, 9:16am UTC](https://internals.rust-lang.org/t/why-not-use-d-ary-heap-inside-rather-than-binary-heap/18765/6 "2023-04-30T09:16:22Z")
Thanks. In the comments of that blog post, the author actually mentioned quaternary heap. > Yes, a quaternary heap will beat this min-max heap. You can already try it by using the d-ary heap from my code and setting D=4. Given that min-max heap is more powerful than binary heap but less performant than quaternary heap, I prefer exposing it as another struct to release its full power rather than using it as the internal implementation of `std::collections::BinaryHeap`. ---
**Author:** ![QuarticCat](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/quarticcat/32/10827_2.png) [@QuarticCat](https://internals.rust-lang.org/u/QuarticCat)\ **Post date:** [April 30, 2023, 9:23am UTC](https://internals.rust-lang.org/t/why-not-use-d-ary-heap-inside-rather-than-binary-heap/18765/7 "2023-04-30T09:23:53Z")
> [BinaryHeap example should show how to make a min-heap. #58174](https://github.com/rust-lang/rust/issues/58174) talks about how the current one being a max-heap isn't inherently obvious. Actually that makes sense from another perspective. If you heap-sort an max-heap, you get an ascending array, which is the default, thus max-heap is the default. As far as I know, C++'s `std::priority_queue` is also a max-heap by default. Off-topic anyway. ---
**Author:** ![user16251](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/user16251/32/10186_2.png) [@user16251](https://internals.rust-lang.org/u/user16251)\ **Post date:** [April 30, 2023, 11:27am UTC](https://internals.rust-lang.org/t/why-not-use-d-ary-heap-inside-rather-than-binary-heap/18765/8 "2023-04-30T11:27:24Z")
Is there anything in the interface of `BinaryHeap` that actually requires it being implemented by a binary heap as opposed to a k-ary heap for higher k? The name is poorly chosen. ---
**Author:** ![scottmcm](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/scottmcm/32/2355_2.png) [@scottmcm](https://internals.rust-lang.org/u/scottmcm)\ **Post date:** [April 30, 2023, 5:51pm UTC](https://internals.rust-lang.org/t/why-not-use-d-ary-heap-inside-rather-than-binary-heap/18765/9 "2023-04-30T17:51:40Z")
> [@QuarticCat](#): > > I prefer exposing it as another struct to release its full power That's where I ended up in the conversation too. I'd opened a PR to stabilize `BinaryHeap::into_iter_sorted`, but ended up withdrawing that PR as the conversation in it made me think the API is too awkward to be worth it: [Stabilize feature(binary\_heap\_into\_iter\_sorted) by scottmcm · Pull Request #76234 · rust-lang/rust · GitHub](https://github.com/rust-lang/rust/pull/76234#issuecomment-708505210) With a new type, it could have `pop_min` and `pop_max` instead of just `pop`, and it could _only_ offer sorted iterators (sending you through `into_vec` or whatever if people want other unsorted access to the items). ---
**Author:** ![matklad](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/matklad/32/12266_2.png) [@matklad](https://internals.rust-lang.org/u/matklad)\ **Post date:** [May 1, 2023, 8:47am UTC](https://internals.rust-lang.org/t/why-not-use-d-ary-heap-inside-rather-than-binary-heap/18765/10 "2023-05-01T08:47:33Z")
FWIW, I think that it would be worth it to (soft) deprecate BinaryHeap, and introduce a MinHeap with faster and less ambiguous API. Deprecating the whole data structure is a tall order, but it does seem that BinaryHeap is uniquely unfortunate: - The API is inconvenient, you almost always want a minheap in practice (the only common exception is sorting, but iirc into\_vec().sort() is faster than into\_sorted\_vec() anyway). - The API is confusing. Nothing in the API tells that this is a max heap - The API is slow. I am not entirely sure, but I think we guarantee somewhere in the API that it’s a binary heap. I don’t think we should do MinMax heap. The motivation for that was that it’s faster, but it’s faster not because it is MinMax, but because it’s n-ary heap. So, just n-ary MinHeap would be the fastest of all. Or, rather, we could add MinMax as I imagine sometimes you do want min-max property, but we should do that after we fix the common variation first. All that being said, it feels like we don’t have too much spare capacity when it comes to the design of stdlib, and this heap of problems doesn’t feel particularly high priority. ---
**Author:** ![dlight](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/dlight/32/8462_2.png) [@dlight](https://internals.rust-lang.org/u/dlight)\ **Post date:** [May 1, 2023, 9:40am UTC](https://internals.rust-lang.org/t/why-not-use-d-ary-heap-inside-rather-than-binary-heap/18765/11 "2023-05-01T09:40:54Z")
Maybe just create `MinHeap` and `MaxHeap` and make `BinaryHeap` be a type alias to `MaxHeap`. Do not deprecate it, do not change anything from the API, but change its internals to not be a binary heap anymore. ---
**Author:** ![2e71828](https://avatars.discourse-cdn.com/v4/letter/2/3e96dc/32.png) [@2e71828](https://internals.rust-lang.org/u/2e71828)\ **Post date:** [May 1, 2023, 9:46am UTC](https://internals.rust-lang.org/t/why-not-use-d-ary-heap-inside-rather-than-binary-heap/18765/12 "2023-05-01T09:46:30Z")
> [@matklad](#): > > I am not entirely sure, but I think we guarantee somewhere in the API that it’s a binary heap. I just read through [the documentation](https://doc.rust-lang.org/std/collections/struct.BinaryHeap.html); aside from the type name, the most explicit mention of the internal algorithm occurs in the preamble (emphasis mine): > A priority queue **implemented with a binary heap**. > > This will be a max-heap. > > It is a logic error for an item to be modified in such a way that the item’s ordering relative to any other item, as determined by the [`Ord`](https://doc.rust-lang.org/std/cmp/trait.Ord.html) trait, changes while it is in the heap. This is normally only possible through interior mutability, global state, I/O, or unsafe code. The behavior resulting from such a logic error is not specified, but will be encapsulated to the `BinaryHeap` that observed the logic error and not result in undefined behavior. This could include panics, incorrect results, aborts, memory leaks, and non-termination. > > As long as no elements change their relative order while being in the heap as described above, the API of `BinaryHeap` **guarantees that the heap invariant¹ remains intact** _i.e. its methods all behave as documented_. For example if a method is documented as iterating in sorted order, that’s guaranteed to work as long as elements in the heap have not changed order, even in the presence of closures getting unwinded out of, iterators getting leaked, and similar foolishness. ¹ "The heap invariant" is not further defined anywhere on this page, either explicitly or by reference. * * * - Documentation of the methods appear to use the phrases "the binary heap" and "the `BinaryHeap`" interchangeably to refer to `self`, but go into no further details about the internals. - Some time complexities are guaranteed by the documentation— I believe these would all be met or exceeded by a d-ary heap: - Push: _O_(1) (amortized) - Pop: _O_(log(_n_)) - Peek: _O_(1) - The top of the heap is consistently referred to as "the greatest item" - Methods that access elements in storage order consistently refer to it as an "arbitrary order" - `into_sorted_vec` explicitly calls it "sorted (ascending) order" - The documentation for some of the experimental methods refer to "heap order," but this is never explicitly defined and not used outside experimental documentation. * * * > [@dlight](#): > > Maybe just create `MinHeap` and `MaxHeap` and make `BinaryHeap` be a type alias to `MaxHeap`. As we have const generics now, it would be possible to define `MaxHeap`and then alias `BinaryHeap` to `MaxHeap<2>`, which should even keep all of the "arbitrary order"s the same. But that risks locking `std` into a particular algorithm again, albeit a better one than before. ---
**Author:** ![system](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/system/32/14092_2.png) [@system](https://internals.rust-lang.org/u/system)\ **Post date:** [July 30, 2023, 9:46am UTC](https://internals.rust-lang.org/t/why-not-use-d-ary-heap-inside-rather-than-binary-heap/18765/13 "2023-07-30T09:46:52Z")
Closed on July 30, 2023, 9:46am UTC This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.