Re: Self reordering list in Python

Paul Rubin wrote:
> "zooko" <zooko@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
Received on Sat Oct 15 04:00:32 2005