October 25, 2021 what's the most efficient way to implement std.container.binaryheap.back()? | ||||
|---|---|---|---|---|
| ||||
 | Hi, https://dlang.org/phobos/std_container_binaryheap.html The binary heap induces structure over the underlying store such that accessing the largest element (by using the front property) is a Ο(1) operation. I'm wondering what's the most efficient (in terms of both speed and memory usage) way to implement std.container.binaryheap.back()? i.e accessing the smallest element. Has anyone done this before? Thanks. | |||
October 25, 2021 Re: what's the most efficient way to implement std.container.binaryheap.back()? | ||||
|---|---|---|---|---|
| ||||
 Posted in reply to mw | On Monday, 25 October 2021 at 04:49:12 UTC, mw wrote: >Hi, https://dlang.org/phobos/std_container_binaryheap.html The binary heap induces structure over the underlying store such that accessing the largest element (by using the front property) is a Ο(1) operation. I'm wondering what's the most efficient (in terms of both speed and memory usage) way to implement std.container.binaryheap.back()? i.e accessing the smallest element. Has anyone done this before? Thanks. I didn't look at the implementation, but the implementations I have looked at are backed by an array (a random access container would do). If so you need to find the min of elements from the largest "one less than a power of two" less than the size of the heap up to the size of heap. However, perhaps an alternative data struct would be better? See e.g. https://en.m.wikipedia.org/wiki/Min-max_heap On Monday, 25 October 2021 at 04:49:12 UTC, mw wrote: | |||
Permalink
Reply