On Wednesday, 5 August 2015 at 18:20:41 UTC, John Colvin wrote:
in my vision, either x.popFront would also create a copy or you
would have to go "auto y = x.nonModifyingView" or similar. What
I don't want is something that copies 10000 elements just to
use x.take(6)
I suggest you rehearse on how a binary heap works. A binary heap
with array storage trades speed for memory compactness, a bit
similar to how quick sort relates to heap sort.
See also: https://en.wikipedia.org/wiki/Binary_heap
The underlying heap array in D's `BinaryHeap` contains both the
data leaves and their inter-orderings in a memory-packed manner.
This makes heaps very space-efficient and running `dup` on the
underlying array is very cheap (in D), especially for value types.
When you pop an element from the heap an in-place reorganisation
(balancing) will be performed on the array. This means `popFront`
will potentially (in the worst case) require a complete copy of
the array in order to not have to modify the original array.
AFAIK, the 10000 elements will always have to be copied even when
we just need x.take(2). Peeking the front (using `front()`) is
O(1), but *popping* the front (to get the next front) in the
range may, in the worst cast, have to require reorganisation of
*all* the 10000 elements.
See also: https://en.wikipedia.org/wiki/Binary_heap#Extract
Please correct me if I'm wrong.
