Is it possible to elegantly create a range over a binary heap?

Gary Willoughby via Digitalmars-d-learn digitalmars-d-learn at puremagic.com
Mon Dec 28 04:58:36 PST 2015


On Sunday, 27 December 2015 at 22:42:21 UTC, Ivan Kazmenko wrote:
> If you implement a struct with range primitives over it, you 
> can use it as a range.
>
> See the second code example in std.container.binaryheap's docs 
> at
> http://dlang.org/phobos/std_container_binaryheap.html#.BinaryHeap.
>
> Or do you mean you want to print variables in order without 
> modifying the array?  Sounds like this would require at least N 
> log N time and N additional memory for an N-element heap anyway 
> (or quadratic time and constant memory).  So, you can just copy 
> the array and exhaust the copied binary heap, getting the same 
> asymptotic complexity: N log N time and N additional memory.
>
> Ivan Kazmenko.

Thanks. I wanted to iterate through the range without modifying 
the original array but like you said the only way to do that is 
by copying the data which is not ideal.

std.container.binaryheap looks like it implements the range 
interface and consumes the original during iteration. I'll 
probably do that too.


More information about the Digitalmars-d-learn mailing list