heapq question

bearophileHUGS at lycos.com bearophileHUGS at lycos.com
Sun Jul 13 00:02:39 CEST 2008


Giampaolo Rodola':
> Even if I avoid to re-heapify() it seems that the first element
> returned by heappop() is always the smaller one.

Yes, the heappop() function keeps the heap invariant, so it will keep
giving you the smallest item.


> 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.

To be an heap it must keep its heap invariant true. The heap functions
keep that invariant. Generally any time you move/delete an item
yourself, you break the invariant, so you don't have an heap anymore
and you need to re-heapify to restore the heap invariant :-)

Bye,
bearophile



More information about the Python-list mailing list