heapq question

[Giampaolo Rodola']

Hi,
this is related to what I'm trying to implement here:

http://groups.google.com/group/comp.lang.python/browse_thread/thread/20796724c1daf1e1#

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(hea p)
>>del heap[4]
>># Am I forced to heapify() the heap here?

Thanks in advance.


--- Giampaolo

http://code.google.com/p/pyftpdlib/

[Duncan Booth]

Re: heapq question

"Giampaolo Rodola'" <gnewsg@gmail.c omwrote:

>
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(hea p)
>>heap

[0, 100, 1, 101, 102, 2, 3]

>>del(heap[4])
>>heap

[0, 100, 1, 101, 2, 3]

>>heapify(hea p)
>>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].

[Giampaolo Rodola']

Re: heapq question

On 12 Lug, 20:15, Duncan Booth <duncan.bo...@i nvalid.invalidw rote:

"Giampaolo Rodola'" <gne...@gmail.c omwrote:
>

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(hea p)
>>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(hea p)

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

Even if I avoid to re-heapify() it seems that the first element
returned by heappop() is always the smaller one.

>>heap = [0, 100, 1, 101, 102, 2, 3]
>>heapify(hea p)
>>heap

[0, 100, 1, 101, 102, 2, 3]

>>del heap[4]
>>heap

[0, 100, 1, 101, 2, 3]

>>heappop(hea p)

0

>>heappop(hea p)

1

>>heappop(hea p)

2

>>heappop(hea p)

3

>>heappop(hea p)

100

>>heappop(hea p)

101

>>heappop(hea p)

Traceback (most recent call last):
File "<stdin>", line 1, in <module>
IndexError: index out of range

>>>

That would be ok for me, as long as heappop() always returns the
smallest item.
Having said that I'd like to understand if there are cases where
deleting or moving an element of the heap, causes heappop() to return
an element which is not the smallest one.


--- Giampaolo

http://code.google.com/p/pyftpdlib/

[bearophileHUGS@lycos.com]

Re: heapq question

Giampaolo Rodola':

Even if I avoid to re-heapify() it seems that the first element
returned by heappop() is always the smaller one.

Yes, the heappop() function keeps the heap invariant, so it will keep
giving you the smallest item.

I'd like to understand if there are cases where
deleting or moving an element of the heap, causes heappop() to return
an element which is not the smallest one.

To be an heap it must keep its heap invariant true. The heap functions
keep that invariant. Generally any time you move/delete an item
yourself, you break the invariant, so you don't have an heap anymore
and you need to re-heapify to restore the heap invariant :-)

Bye,
bearophile

[=?ISO-8859-1?Q?=22Martin_v=2E_L=F6wis=22?=]

Re: heapq question

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:

def remove_at_index _n(heap, n):
if n == len(heap)-1:
return heap.pop()
result = heap[n]
heap[n] = heap.pop()
heapq._siftup(h eap, n)
return result

The time complexity for that operation is O(log(len(heap) )).

HTH,
Martin

[Giampaolo Rodola']

Re: heapq question

On 13 Lug, 19:31, "Martin v. Löwis" <mar...@v.loewi s.dewrote:

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:
>
def remove_at_index _n(heap, n):
    if n == len(heap)-1:
        return heap.pop()
    result = heap[n]
    heap[n] = heap.pop()
    heapq._siftup(h eap, n)
    return result
>
The time complexity for that operation is O(log(len(heap) )).
>
HTH,
Martin

Thanks, by doing some quick benchamrks it seems 20% faster than using
heapify().
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(hea p)
>>heap

[0, 2, 1, 4, 5, 6, 7, 8, 9]

>>heap[4] = 12

--- Giampaolo

http://code.google.com/p/pyftpdlib/

[Duncan Booth]

Re: heapq question

"Giampaolo Rodola'" <gnewsg@gmail.c omwrote:

Thanks, that's what I wanted to know.
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.
Thanks for your help anyway.
>
>

There could be suitable functions, but there aren't any. I *think* this
would work (untested):

def popitem(heap, pos):
if pos == 0:
return heappop(heap)
if pos == len(heap)-1:
return heap.pop(pos)
res = heap[pos]
heap[pos] = heap.pop()
heapq._siftup(h eap, pos)
return res

the catch is that _siftup is written in Python whereas the publicly exposed
heapq functions are written in C, so although in theory this is 'more
efficient' than calling heapify() on the entire heap it may actually be
slower.

Bottom line though is that heaps aren't really suitable for timeouts.

[Miles]

Re: heapq question

On Sun, Jul 13, 2008 at 4:16 PM, Duncan Booth
<duncan.booth@i nvalid.invalidw rote:

"Giampaolo Rodola'" <gnewsg@gmail.c omwrote:

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

There could be suitable functions, but there aren't any.
...
Bottom line though is that heaps aren't really suitable for timeouts.

I would argue that heaps in general are ideally suited for timeouts;
it's just that the Python heapq implementation is lacking if you ever
need to cancel a timeout before it expires.

-Miles