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

Ivan Kazmenko via Digitalmars-d-learn digitalmars-d-learn at puremagic.com
Sun Dec 27 14:42:21 PST 2015


On Sunday, 27 December 2015 at 20:01:47 UTC, Gary Willoughby 
wrote:
> On Sunday, 27 December 2015 at 17:23:35 UTC, Gary Willoughby 
> wrote:
>> I have a binary tree storing ints implemented using an array. 
>> The internal state looks like this:
>>
>> 8,7,6,4,1,3,5,2
>>
>> When extracting this data, it is returned as 8,7,6,5,4,3,2,1.
>>
>> Is it possible to elegantly add a range on top of the internal 
>> state to return the correct value order I would expect when 
>> extracting? Is there an algorithm documented somewhere for 
>> doing this?
>
> Some explanatory reference:
>
> https://en.wikipedia.org/wiki/Binary_tree#Arrays

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.


More information about the Digitalmars-d-learn mailing list