On Thursday, 6 August 2015 at 08:44:17 UTC, Per Nordlöw wrote:
On Wednesday, 5 August 2015 at 18:20:41 UTC, John Colvin wrote:
[...]
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.
Worst case for getting root off a binary heap is O(log(N)),
copying the whole thing is O(N).
In practice the copy may be very cheap, but it does mean more
memory usage and won't scale to very large N. Perhaps it's an OK
tradeoff, but you want to be careful.
