www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - How do you use BinaryHeap with Array (or just make a growable heap)?

reply Magnus Lie Hetland <magnus hetland.org> writes:
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
Mar 28 2011
parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
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
Mar 28 2011
parent Magnus Lie Hetland <magnus hetland.org> writes:
On 2011-03-28 20:24:55 +0200, Jonathan M Davis said:


 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.


Hm. I can't even get the slicing to work:

/path/to/phobos/std/container.d(2436): Error: function 
std.container.Array!(uint).Array.Range.opSlice (uint a, uint b) is not 
callable using argument types ()


 Glancing at BinaryHeap, it'll work with arrays though, so you don't 
 need to use Array.


Hm. The docs say "If Store is a range, the BinaryHeap cannot grow 
beyond the size of that range. If Store is a container that supports 
insertBack, the BinaryHeap may grow by adding elements to the 
container."

So it seems that a container (such as Array, which has insertBack) 
should be usable, according to the docs. And an array/slice would not 
be growable. (At least, it isn't growable in practice.) See also:

  
http://www.digitalmars.com/d/archives/digitalmars/D/std.algorithm.BinaryHeap_88811.html

What 

I'm looking for is a completely standard priority queue, where I can 
add and remove objects, and not have to know the maximum size 
beforehand.

I'd also like to have tuple entries, but it seems that BinaryHeap has 
trouble with that as well...


 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.


Yeah, it seems to be. At the moment, I've just reimplemented BinaryHeap 
myself (with a subset of the Phobos API), so that it can handle arrays 
of tuples (which I couldn't get std.container.BinaryHeap to accept). I 
then wrapped it in a PriorityQueue class, which takes care of resizing 
the array (and having BinaryHeap switch to the possibly reallocated new 
one).

Not an ideal solution, but at least it works.

-- 
Magnus Lie Hetland
http://hetland.org
Mar 28 2011