heapq question

[Duncan Booth]

"Giampaolo Rodola'" <gnewsg at gmail.com> wrote:

> Thanks, that's what I wanted to know.
> 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.
> Thanks for your help anyway.
> 
> 
There could be suitable functions, but there aren't any. I *think* this 
would work (untested):

def popitem(heap, pos):
    if pos == 0:
        return heappop(heap)
    if pos == len(heap)-1:
        return heap.pop(pos)
    res = heap[pos]
    heap[pos] = heap.pop()
    heapq._siftup(heap, pos)
    return res

the catch is that _siftup is written in Python whereas the publicly exposed 
heapq functions are written in C, so although in theory this is 'more 
efficient' than calling heapify() on the entire heap it may actually be 
slower.

Bottom line though is that heaps aren't really suitable for timeouts.