heapq question

Duncan Booth duncan.booth at invalid.invalid
Sat Jul 12 20:15:28 CEST 2008

```"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?
>

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].

```