heapq question

[Duncan Booth]

"Giampaolo Rodola'" <gnewsg 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].