heapq question

[Giampaolo Rodola']

On 13 Lug, 22:35, Miles <semantic... at gmail.com> wrote:
> On Sun, Jul 13, 2008 at 3:05 PM, Giampaolo Rodola' <gne... at gmail.com> wrote:
> > On 13 Lug, 19:31, "Martin v. Löwis" <mar... at v.loewis.de> wrote:
> >> > I understand that heapq is not that efficient to implement timeouts as
> >> > I thought at first.
> >> > It would have been perfect if there were functions to remove arbitrary
> >> > elements withouth needing to re-heapify() the heap every time.
>
> >> It is efficient for that - you just need to use it correctly.
>
> >> To remove the nth element from a heap, replace it with the last element,
> >> and then _siftup that element:
>
> >> The time complexity for that operation is O(log(len(heap))).
>
> The problem is that in order to remove an arbitrary element from a
> heap, you usually have to do an O(n) linear search in order to find it
> first, since you can't know ahead of time which index an arbitrary
> element is at.  (You can, actually, but only if your heap
> implementation somehow notifies the elements of their new index when
> it moves them in the heap, which the Python heapq module doesn't do,
> so you'd have to write your own heap implementation.)
>
> > And if instead of removing an element I'd want to change its value?
> > E.g.:
>
> >  >>> heap = [0, 2, 1, 4, 5, 6, 7, 8, 9]
> >  >>> heapify(heap)
> >  >>> heap
> >  [0, 2, 1, 4, 5, 6, 7, 8, 9]
> >  >>> heap[4] = 12
>
> Don't do that; you must first remove the element and then reinsert it.
>
> -Miles

That seems to be slower than re-heapifying() the heap.
The code I used (which is probably wrong):

    def reset(self):
        """Reschedule this call resetting the current countdown."""
        assert not self.cancelled, "Already cancelled"
        self.timeout = time.time() + self.__delay
        n = heap.index(self)
        if n == len(heap) - 1:
            heap.pop()
        else:
            heap[n] = heap.pop()
            heapq._siftup(heap, n)
        heapq.heappush(heap, self)


Moreover I have the feeling that doing such thing requires a different
code whether the new value I use as replacement is lower or higher in
comparison to the older one.
Am I right?


--- Giampaolo
http://code.google.com/p/pyftpdlib/