Creating a Priority Queue: An Adventure

[via Digitalmars-d-learn]

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.