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
