heapq question

[Miles]

On Sun, Jul 13, 2008 at 3:05 PM, Giampaolo Rodola' <gnewsg at gmail.com> wrote:
> On 13 Lug, 19:31, "Martin v. Löwis" <mar... at v.loewis.de> wrote:
>> > I understand that heapq is not that efficient to implement timeouts as
>> > I thought at first.
>> > It would have been perfect if there were functions to remove arbitrary
>> > elements withouth needing to re-heapify() the heap every time.
>>
>> It is efficient for that - you just need to use it correctly.
>>
>> To remove the nth element from a heap, replace it with the last element,
>> and then _siftup that element:
>>
>> The time complexity for that operation is O(log(len(heap))).

The problem is that in order to remove an arbitrary element from a
heap, you usually have to do an O(n) linear search in order to find it
first, since you can't know ahead of time which index an arbitrary
element is at.  (You can, actually, but only if your heap
implementation somehow notifies the elements of their new index when
it moves them in the heap, which the Python heapq module doesn't do,
so you'd have to write your own heap implementation.)

> And if instead of removing an element I'd want to change its value?
> E.g.:
>
>  >>> heap = [0, 2, 1, 4, 5, 6, 7, 8, 9]
>  >>> heapify(heap)
>  >>> heap
>  [0, 2, 1, 4, 5, 6, 7, 8, 9]
>  >>> heap[4] = 12

Don't do that; you must first remove the element and then reinsert it.

-Miles