On 13 Lug, 11:35, Duncan Booth <[EMAIL PROTECTED]> wrote: > "Giampaolo Rodola'" <[EMAIL PROTECTED]> wrote: > > Having said that I'd like to understand if there are cases where > > deleting or moving an element of the heap, causes heappop() to return > > an element which is not the smallest one. > > Yes, of course there are: any time you delete element 0 of the heap you can > do that. > > >>> heap = [0, 2, 1, 4, 5, 6, 7, 8, 9] > >>> heapify(heap) > >>> heap > > [0, 2, 1, 4, 5, 6, 7, 8, 9] > > >>> del heap[0] > >>> heappop(heap) > 2 > > By definition, element 0 is always the smallest but the next two elements > could be in any order. If you delete an element other than 0 then the next > pop won't be guaranteed to work. > > If you delete an element other than 0 the very next pop will work, but the > heap conditions won't necessarily be restored so subsequent elements may > come out in the wrong order. A simple example: > > >>> heap = [0, 1, 3, 4, 2, 5] > >>> heapify(heap) > >>> heap > [0, 1, 3, 4, 2, 5] > >>> del heap[1] > >>> heappop(heap), heappop(heap), heappop(heap) > > (0, 3, 2)
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. --- Giampaolo http://code.google.com/p/pyftpdlib/ -- http://mail.python.org/mailman/listinfo/python-list
