Binary heap method to update an entry.

[Pelle Månsson]

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?