Creating a Priority Queue: An Adventure

[John Colvin via Digitalmars-d-learn]

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.