Christopher T King
squirrel at WPI.EDU
Tue Jul 27 16:06:12 CEST 2004
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
More information about the Python-list