"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) -- http://mail.python.org/mailman/listinfo/python-list
