heapq question

Giampaolo Rodola' gnewsg at gmail.com
Sun Jul 13 11:17:07 EDT 2008


On 13 Lug, 11:35, Duncan Booth <duncan.bo... at invalid.invalid> wrote:
> "Giampaolo Rodola'" <gne... 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)

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/



More information about the Python-list mailing list