Binary heap method to update an entry.

Andrei Alexandrescu SeeWebsiteForEmail at erdani.org
Thu Dec 16 07:53:08 PST 2010


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


More information about the Digitalmars-d mailing list