Hi,

I wanted to have a binary heap where I can update entries and restore the heap structure.

1. First I observed that due to the implementation of std.container.BinaryHeap, keeping track of the position of a certain value in the heap cannot be done directly, but it would be helpful to pass a "Swapper" object (or function) to the methods that may change the order of the elements such that this Swapper is called for every swap() operation such that the user of the BinaryHeap can keep track of the permutation.

2. I tried to create a heap structure on my own, using std.container.Array as a store. Of course, it I also needs to perform swap operations, but the following did not work:

std.algorithm.swap(arrayInstance[i], arrayInstance[j]);

Also there is no usable swap() method of Array. So do I really have to perform the swap on my own? I mean, 3 lines of code aren't that much but I really expected an easy way.

3. For my structure I wanted to check the heap structure in an invariant(). Unfortunately, accessing stored elements of Array is no const operation, hence I could not implement such an invariant.

Maybe I'm not using it correctly, so any help or comments would be nice.

Best regards,

Matthias

On 03/08/2012 03:21 AM, Matthias Walter wrote:
> Hi,
>
> I wanted to have a binary heap where I can update entries and restore
> the heap structure.
>

<shameless plug>

I totally built this functionality in to multi_index's red black tree, hash table, and heap indeces.

-------------------------------------------------
alias MultiIndexContainer!(int, IndexedBy!(Heap!())) C1;

C1 c = new C1;
c.insert([1,2,3,4,5]);

auto rng = c[];

<point rng to item you want>

// modify the value, then heap is restored by container
c.modify(rng, (ref int i){ i = 42; });
-------------------------------------------------

If you have a more complicated type, you can also set up a signals and slots thing so you can keep a reference to your object and modify it and the container will automatically fix the heap without you having to use modify.

I also started on converting ranges from one index to ranges of another for e.g. using a hash table to reference your value/object, but I'm waiting on compiler bugs.

</shameless plug>