Home Original page

How to remove item from heap efficiently?

Robin Becker robin at reportlab.com
Wed Jan 13 11:40:29 EST 2016 
On 13/01/2016 15:34, srinivas devaki wrote:
> On Wed, Jan 13, 2016 at 4:50 PM, Cem Karan <cfkaran2 at gmail.com> wrote:
>>
>> Is that so?  I'll be honest, I never tested its asymptotic performance, I just assumed that he had a dict coupled with a heap somehow, but I never looked into the code.
>>
>
> I have just tested the code, the aymptotic performance is O(log(n))
> for all operations. Infact the code is very simple to understand,
> technically the heapdict class is composed of a dict and heap, each element of
> heap is a mutable list and dict stores references to that mutable list,
> so that a specific element can be deleted in O(log(n))
>
is this true? I looked at https://wiki.python.org/moin/TimeComplexity and it 
says that dict.get which I assume is used for accessing the heapq delete point 
can be large (the average time is O(1), but amortized over a lot of accesses can 
be O(n)). Apparently the history of sets/gets can affect individual times quite 
a lot. I seem to remember there was some kind of hashing attack against python 
dicts that would use up large amounts of time, but I guess that's now fixed.
-- 
Robin Becker
More information about the Python-list mailing list