Re: Binary heap method to update an entry.
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?
Re: Binary heap method to update an entry.
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
Re: Binary heap method to update an entry.
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
Re: Binary heap method to update an entry.
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
Re: Binary heap method to update an entry.
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. Matthias
Re: Binary heap method to update an entry.
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
Binary heap method to update an entry.
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
