On 12/16/2010 04:53 PM, 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.
Obviously, if you have already changed the element, you may always call
update with an empty lambda.
Andrei
Isn't passing the index slightly weird? Shouldn't it use a predicate, or
something?
Looks to me like I'd be doing something like this:
auto arr = myheap.release();
auto i = indexOf!pred(arr);
myheap.assume(arr);
myheap.update!"a.fiddle()"(i);
Would I be doing it wrong?
