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?
>
> 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].
More information about the Python-list
mailing list