what's the most efficient way to implement std.container.binaryheap.back()?
JG
someone at somewhere.com
Mon Oct 25 11:30:16 UTC 2021
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:
More information about the Digitalmars-d-learn
mailing list