www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Binary heap method to update an entry.

reply Matthias Walter <xammy xammy.homelinux.net> writes:
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
Dec 15 2010
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Dec 16 2010
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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?

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
Dec 16 2010
next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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?

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.

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
Dec 16 2010
prev sibling parent =?UTF-8?B?UGVsbGUgTcOlbnNzb24=?= <pelle.mansson gmail.com> writes:
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?

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?
Dec 17 2010
prev sibling parent Matthias Walter <xammy xammy.homelinux.net> writes:
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?

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.

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
Dec 16 2010
prev sibling parent Matthias Walter <xammy xammy.homelinux.net> writes:
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?

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
Dec 16 2010