You can remove the i-th element from a heap quite easily:
h[i] = h[-1] h.pop() heapq.heapify(h)
Just replace the element you want to remove with the last element and remove the last element then re-heapify the heap. This is O(n), if you want you can do the same thing in O(log(n)) but you'll need to call a couple of the internal heapify functions, or better as larsmans pointed out just copy the source of _siftup/_siftdown out of heapq.py into your own code:
h[i] = h[-1] h.pop() heapq._siftup(h, i) heapq._siftdown(h, 0, i)
Note that in each case you can't just do
h[i] = h.pop() as that would fail if
i references the last element. If you special case removing the last element then you could combine the overwrite and pop.
Note that depending on the typical size of your heap you might find that just calling
heapify while theoretically less efficient could be faster than re-using
_siftdown: a little bit of introspection will reveal that
heapify is probably implemented in C but the C implementation of the internal functions aren't exposed. If performance matter to you then consider doing some timing tests on typical data to see which is best. Unless you have really massive heaps big-O may not be the most important factor.
Edit: someone tried to edit this answer to remove the call to
_siftdown with a comment that:
_siftdown is not needed. New h[i] is guaranteed to be the smallest of the old h[i]'s children, which is still larger than old h[i]'s parent (new h[i]'s parent). _siftdown will be a no-op. I have to edit since I don't have enough rep to add a comment yet.
What they've missed in this comment is that
h[-1] might not be a child of
h[i] at all. The new value inserted at
h[i] could come from a completely different branch of the heap so it might need to be sifted in either direction.
Also to the comment asking why not just use
sort() to restore the heap: calling
_siftdown are both O(log n) operations, calling heapify is O(n). Calling
sort() is an O(n log n) operation. It is quite possible that calling sort will be fast enough but for large heaps it is an unnecessary overhead.