Binary heap method to update an entry.

[Matthias Walter]

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?

Matthias Walter