"Giampaolo Rodola'" <[EMAIL PROTECTED]> 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]. -- http://mail.python.org/mailman/listinfo/python-list
