Binary heap method to update an entry.

[Andrei Alexandrescu]

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?

Andrei