Binary heap method to update an entry.

[Matthias Walter]

On 12/16/2010 10:53 AM, Andrei Alexandrescu wrote:
> On 12/16/10 7:55 AM, Matthias Walter wrote:
>> On 12/16/2010 04:17 AM, Andrei Alexandrescu wrote:
>>> On 12/15/10 10:21 PM, Matthias Walter wrote:
>>>> Hi all,
>>>>
>>>> I uploaded [1] a patch for std.container to use BinaryHeap as a
>>>> priority
>>>> queue. For the latter one it is often necessary to change a value
>>>> (often
>>>> called decreaseKey in a MinHeap). For example, Dijkstra's shortest
>>>> path
>>>> algorithm would need such a method. My implementation expects that the
>>>> user calls the "update" method after changing the entry in the
>>>> underlying store.
>>>>
>>>> My method works for value-decrease and -increase, but one might
>>>> want to
>>>> split this functionality into two methods for efficiency reasons.
>>>> But I
>>>> thought it'll be better, because one can change the MaxHeap to be a
>>>> MaxHeap by changing the template alias parameter, but this wouldn't
>>>> change the method names :-)
>>>>
>>>> The patch is against current svn trunk.
>>>>
>>>> [1]
>>>> http://xammy.xammy.homelinux.net/files/BinaryHeap-PriorityQueue.patch
>>>
>>> A better primitive is to define update to take an index and a new
>>> value, such that user code does not need to deal simultaneously with
>>> the underlying array and the heap. No?
>> Well, I thought of the case where you have an array of structs and use a
>> custom less function for ordering. There you might not have a new value,
>> i.e. a replaced struct, but just a minor change internally. But I see
>> your idea, in most cases you would just call update after replacing your
>> array entry... Could we provide both, maybe?
>
> Good point. Here's what I suggest:
>
> /**
>   Applies unary function fun to the element at position index, after
> which moves that element to preserve the heap property. (It is assumed
> that fun changes the element.) Returns the new position of the element
> in the heap.
>
> Example:
>
> ----
> int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];
> auto h = heapify(a);
> assert(equal(a, [ 16, 14, 10, 9, 8, 7, 4, 3, 2, 1 ]));
> h.update!"a -= 5"(1);
> assert(equal(a, [ 16, 10, 9, 9, 8, 7, 4, 3, 2, 1 ]));
> ----
> */
> size_t update(alias fun)(size_t index);
>
> Let me know of what you think, and thanks for contributing. When using
> unaryFun inside update, don't forget to pass true as the second
> argument to unaryFun to make sure you enact pass by reference.
Good idea. I like the interface!

Btw, can I then call a routine in the string, too? Like

h.update!"a.updatePriority()"(1);

Although this does look ugly, so separating the call would probably make
more sense.

Matthias