std.algorithm.BinaryHeap

[Andrei Alexandrescu]

bearophile wrote:
> This may be a dumb question: How do you push/add an item to such heap
> (to translate the heappush)? I have found no info in the docs.

It's a very good question. BinaryHeap intently lacks a way to increase 
its length because it's meant to be a structuring over an existing 
range, not an autonomous one. As such, BinaryHeap is pretty obtuse to 
use (you need to make an array first and then bind BinaryHeap to it).

Once there's a clear way to express topology in Phobos, BinaryHeap will 
use it. Currently there's an embryo of topology-related choices in 
std.range:

enum Topology
{
/** The range cannot change the container's topology (whereas it can
     change its content). This is useful if e.g. the container must
     control creation and destruction of its slots.
  */
     fixed,
/** The range can change the underlying container's structure. This is
     useful if the range is free-floating and is not owned by any
     container.
  */
     flexible
}

These topology choices are used with SListRange (independent, growable 
singly-linked list vs. a range looking at a different singly-linked 
list). If the notion of topology turns out to be a good design, today's 
BinaryHeap is Topology.fixed, whereas a BinaryHeap that is 
Topology.flexible can grow no problem.


Andrei