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
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
parent reply 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?


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


 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
Dec 16 2010
next sibling parent reply 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?


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


 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
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?


 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?
Dec 17 2010