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:
