Creating a Priority Queue: An Adventure

DarthCthulhu via Digitalmars-d-learn digitalmars-d-learn at puremagic.com
Wed Aug 5 13:41:39 PDT 2015


On Wednesday, 5 August 2015 at 09:04:54 UTC, Nordlöw wrote:
> On Wednesday, 5 August 2015 at 01:02:56 UTC, DarthCthulhu wrote:
>> I must be doing something really stupid here, but I have no 
>> clue what it is. Anyone know?
>
>
> For functional behaviour I prefer a postblit that duplicates 
> the underlying BinaryHeap.
>
> https://github.com/nordlow/justd/blob/master/priority_queue.d
>
> Now the foreach won't consume the queue.

Oh, neat! I stumbled on the same thing (making a .dup of the 
BinaryHeap), but didn't know about the postblit. That makes 
things simplier.

>
> This will however duplicate the underlying array aswell, which 
> is probably not what we want. How do we avoid this?

I was wondering that, myself, when I stumbled on the .dup 
solution. My first thought was to instantiate a templated Array! 
first, then use BinaryHeap.assume or .acquire to make it a 
BinaryHeap while also keeping a reference to the underlining 
array. Then one could just return the array reference in a 
separate function rather than destructively iterating through the 
BinaryHeap.

My experiments didn't bear this out, however. Maybe I'm 
misunderstanding what the .assume and .acquire functions do?

Incidentally, I also discovered the wonderful opDot function 
which allows the PriorityQueue to shunt most of the work down to 
the BinaryHeap directly.

         // Forward most function calls to the underlying queue.
     	BinaryHeap!(Array!(PV), predicate)* opDot() {
         	return &_q;
     	}

> Yeah, I think there is no way to "traverse" a binary heap in 
> order without manipulating it. However, you can print the 
> underlying storage.

There's a way to get at the underlining store? I couldn't find 
any means to do so in the BinaryHeap documentation.

>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)

Yeah, that's it exactly!


More information about the Digitalmars-d-learn mailing list