• mw (11/11) Oct 24 2021 Hi,
• JG (9/20) Oct 25 2021 I didn't look at the implementation, but the implementations I

mw <mingwu gmail.com> writes:

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.

JG <someone somewhere.com> writes:

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: