Self reordering list in Python

zooko zooko at zooko.com
Fri Sep 30 18:17:49 CEST 2005


Paul Rubin wrote:
> "zooko" <zooko at zooko.com> writes:
> > I haven't benchmarked it against Evan Podromou's heap implementation
> > yet, but obviously inserting and removing things from a heapq heap is
> > O(N).
>
> Good heavens, I should hope not.  The whole point of heaps is that
> those operations are O(log(N)).

Oh, you are right --  Python's heapq implementation does not naively do
list.pop(0).

How silly of me to think that Kevin O'Connor, Tim Peters, and Raymond
Hettinger would be so silly.

Regards,

Zooko




More information about the Python-list mailing list