heapq question

[Giampaolo Rodola']

On 12 Lug, 20:15, Duncan Booth <duncan.bo... at invalid.invalid> wrote:
> "Giampaolo Rodola'" <gne... at gmail.com> wrote:
>
> > My question is the following: is it safe to avoid to re-heapify() a
> > heap when I remove or move an element which is not the first one?
> > Example:
>
> >>>> from heapq import *
> >>>> heap = [2,4,6,7,1,2,3]
> >>>> heapify(heap)
> >>>> del heap[4]
> >>>> # Am I forced to heapify() the heap here?
>
> > Thanks in advance.
>
> No, it is not safe to avoid re-heapifying.
>
> After you call heapify the list is ordered such that for any 'n' in the
> range 1..len(heap)//2 it is the case that heap[n-1] <= heap[2*n-1] and when
> heap[2*n] exists heap[n-1] <= heap[2*n].
>
> So:
>
> >>> heap = [0, 100, 1, 101, 102, 2, 3]
> >>> heapify(heap)
> >>> heap
>
> [0, 100, 1, 101, 102, 2, 3]>>> del(heap[4])
> >>> heap
>
> [0, 100, 1, 101, 2, 3]>>> heapify(heap)
> >>> heap
>
> [0, 2, 1, 101, 100, 3]
>
> after deleting heap[4] it is no longer the case that heap[1] >= heap[4] as
> the old heap[5] was a child of heap[2] not of heap[1].

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

>>> heap = [0, 100, 1, 101, 102, 2, 3]
>>> heapify(heap)
>>> heap
[0, 100, 1, 101, 102, 2, 3]
>>> del heap[4]
>>> heap
[0, 100, 1, 101, 2, 3]
>>> heappop(heap)
0
>>> heappop(heap)
1
>>> heappop(heap)
2
>>> heappop(heap)
3
>>> heappop(heap)
100
>>> heappop(heap)
101
>>> heappop(heap)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
IndexError: index out of range
>>>


That would be ok for me, as long as heappop() always returns the
smallest item.
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.


--- Giampaolo
http://code.google.com/p/pyftpdlib/