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

[Jonathan M Davis]

On 2011-03-28 05:35, Magnus Lie Hetland wrote:
> 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?

Well, Array definitely shouldn't be a random access range. The range for it 
(which you'd typically get by slicing it) would be random access, but the 
container itself isn't a range of any kind. Containers aren't ranges (barring 
the oddities of dynamic arrays). I've never used BinaryHeap, but glancing at 
it, my guess would be that the correct solution (if you want to use Array with 
it) is to create an Array and then pass its range to heapify:

Array!uint a;
//... put stuff in a.
auto heap = heapify(a[]);

I'm not sure if that's growable or not though. Glancing at BinaryHeap, it'll 
work with arrays though, so you don't need to use Array. I don't know what the 
ideal container to use with a BinaryHeap is though. Also, in my experience, 
Array is pretty buggy at this point, so I'm not sure how far you'll get with 
it.

- Jonathan M Davis