Growable BinaryHeap: use w/Array?

Magnus Lie Hetland magnus at hetland.org
Sun Mar 6 05:58:10 PST 2011


On 2011-03-06 14:37:19 +0100, Magnus Lie Hetland said:

> Just wondering: If I want a growable binary heap (I'd be open to other 
> priority queue structures, for that matter ;), is the standard way in D 
> (w/Phobos) to combine std.container.BinaryHeap with std.container.Array?

Another thing ... when I use priority queues, I'm usually not 
interested in just having a set of priorities -- the payload data is 
what it's all about. So I thought I'd just use an Array of Tuples, 
managed by BinaryHeap (possibly with a custom comparison, to avoid 
comparing the payloads). But perhaps that's not a good idea?

When I try

    alias Tuple!(real,int) Entry;
    Array!Entry Q;

that works just fine. However, if I try

    alias Tuple!(real,int) Entry;
    Array!Entry Q;

then I get the following errors:

container.d(1549): Error: this for _data needs to be type Array not 
type Payload
container.d(1550): Error: this for _data needs to be type Array not 
type Payload
container.d(1551): Error: this for _data needs to be type Array not 
type Payload

It seems the lines that are being referred to are

    GC.removeRange(_data._payload.ptr);
    free(_data._payload.ptr);
    _data._payload = newPayload;

though I may be wrong about that.

Is this a bug in Array? Am I using it wrong? And what would be the 
recommended "best practice" for a priority queue with payload data in D 
(using Phobos)? (I could just write one myself, but that seems sort of 
wasteful ;)

-- 
Magnus Lie Hetland
http://hetland.org



More information about the Digitalmars-d-learn mailing list