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