Sorted List

[Christopher T King]

On Tue, 27 Jul 2004, Delaney, Timothy C (Timothy) wrote:

> Dan wrote:
> 
> > I like the sets type in python 2.4 but it has one major limitation,
> > it is an unordered collection. 
> > 
> > I needed a container more like a list, but sorted so that searches
> > are fast and ensure elements are in a specifc order. This is very
> > useful for 'fuzzy logic' type searching. I could not find any
> > container in Python that fits this criteria, nor could I find one in
> > the vault so I created SortedList.    
> 
> Check the 'heapq' standard library module.

heapq only works if you only ever want to access the smallest element in 
the list -- it doesn't keep the list sorted linearly, but is rather a 
linear representation of a sorted binary tree.

If you want to maintain a true sorted list, use the 'bisect' module.  It 
uses array bisection to insert, remove and access items.  It is slower 
than heapq though, (O(n) for insert & remove, O(log n) for access using 
bisect, as opposed to O(log n) and O(1) respectively for heapq), so use 
heapq if you only need to access the smallest (or 'best') item in the 
list.