gnewsg at gmail.com
Sun Jul 13 21:05:07 CEST 2008
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))).
Thanks, by doing some quick benchamrks it seems 20% faster than using
And if instead of removing an element I'd want to change its value?
>>> heap = [0, 2, 1, 4, 5, 6, 7, 8, 9]
[0, 2, 1, 4, 5, 6, 7, 8, 9]
>>> heap = 12
More information about the Python-list