alwayssortedlist (was Re: On PEP 322 (ireverse))

[Ian McMeans]

Not only is it not effective, but heaps don't keep their elements in
sorted order... so if you wanted a list to stay sorted, heaps aren't
what you want. They're great for finding the smallest element
repeatedly, but not for i'th order statistics in general.

>>> import heapq
>>> h = [1,3,2,4]
>>> heapq.heapify(h)
>>> h
[1, 3, 2, 4]
>>> h = [4,3,1,2]
>>> heapq.heapify(h)
>>> h
[1, 2, 4, 3]
>>> h.sort()
>>> h
[1, 2, 3, 4]


Alex Martelli <aleax at aleax.it> wrote in message news:<ff6ob.379033$R32.12566818 at news2.tin.it>...
> Bengt Richter wrote:
>    ...
> >>Perfectly right.  If you DO want a listoid container that keeps its
> >>elements sorted, that's not hard to make for yourself.  There are
>  ...
> > No comments on the heapq module?
> 
> It can often offer a good _alternative_ to "a listoid container that keeps
> its elements sorted" -- keeping them as a heap is cheaper than keeping them
> sorted.  But "if you DO want" them sorted, so that at any time accessing
> mycontainer[x] gives me the x-th smallest item in mycontainer, heapq isn't
> gonna be very effective.
> 
> There are many good alternatives to "keeping the elements sorted", and
> heapq may well help implement some of them, but I wasn't discussing the
> alternatives -- just the implementation strategies under the assumption
> that the specs DO call for "always sorted".
> 
> 
> Alex