How do you use BinaryHeap with Array (or just make a growable heap)?

Magnus Lie Hetland magnus at hetland.org
Mon Mar 28 05:35:18 PDT 2011


I need a (growable) binary heap, and I'm trying to avoid writing one 
myself (which isn't too hard, of course :) ... but for some reason I 
can't figure out how to use Phobos to do it.

I've seen stated (e.g., by Andrei and in the docs) that the standard 
way is combining BinaryHeap with an Array. Which is fine with me. 
Except I can't make it work. E.g., I try:

  Array!uint A;
  auto Q = heapify(A);

The error is

/path/to/phobos/std/container.d(2658): Error: template instance 
BinaryHeap!(Array!(uint)) does not match template declaration 
BinaryHeap(Store,alias less = "a < b") if (isRandomAccessRange!(Store) 
|| isRandomAccessRange!(typeof(Store.init[])))
/path/to/phobos/std/container.d(2658): Error: BinaryHeap!(Array!(uint)) 
is used as a type

When I check it out, it seems that isRandomAccessRange!(Array!uint) 
returns false (and it doesn't, AFAIK, have an init), which means that 
the error makes sense.

Does this mean...

1. That Array isn't, and shouldn't be, a random access range?
2. That Array can't, and shouldn't be (despite official statements to 
the contrary) be used with BinaryHeap?

(I suspect the answer to both is "you're doing it wrong" ;)

And, of course, my main question:

3. How do you (canonically) make a growable heap using Phobos?

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



More information about the Digitalmars-d-learn mailing list