heapq question

[Giampaolo Rodola']

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:
>
> def remove_at_index_n(heap, n):
>     if n == len(heap)-1:
>         return heap.pop()
>     result = heap[n]
>     heap[n] = heap.pop()
>     heapq._siftup(heap, n)
>     return result
>
> The time complexity for that operation is O(log(len(heap))).
>
> HTH,
> Martin


Thanks, by doing some quick benchamrks it seems 20% faster than using
heapify().
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



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