On 13 Lug, 19:31, "Martin v. Löwis" <[EMAIL PROTECTED]> 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/ -- http://mail.python.org/mailman/listinfo/python-list
