heapq question

Duncan Booth duncan.booth at invalid.invalid
Sun Jul 13 05:35:03 EDT 2008


"Giampaolo Rodola'" <gnewsg at gmail.com> 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)




More information about the Python-list mailing list