what's the most efficient way to implement std.container.binaryheap.back()?

[JG]

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: