heapq question

["Martin v. Löwis"]

> 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