Binary heap method to update an entry.

[Andrei Alexandrescu]

On 12/16/10 10:06 AM, Matthias Walter wrote:
> 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.

That would work, and if you find the string unpalatable, use a real lambda:

h.update!((a) { a.updatePriority(); })(1);


Andrei