[NEWBIE] Priority Queue in Python

[Tim Peters]

[David Boeren, timing priority queues]

Some notes:

Three of your Python priority queue guys have the extra burden (compared to
your Python insert_priority4 and your Java insert_priority) of mucking
around with an extra key_index argument.  Stick to the same thing
throughout.

Effort devoted to timing naive algorithms is better spent dreaming up better
algorithms.  "The usual" naive priority queue in Python uses the std bisect
module directly:

import bisect
bisect.insort(list, item)

Then finding the place to insert is an O(log(len(list))) time operation,
although doing the actual insert remains O(len(list)) time, but where the
latter is at full C speed.  While faster then doing a linear search, if your
priority queues are going to get large, this is a disastrous approach
regardless of language.

Note that Python compares tuples lexicographically (strings and lists too),
so even if the item is a tuple this works fine provided item[0] is the
primary key.

If your benchmarks are typical of your expected access pattern (i.e.,
nothing but inserts -- no lookups), or an approximation to your expected
access pattern (perhaps lots of inserts followed by lots of lookups), it
would be much faster to do the insert via

list.append(item)

and do

list.sort()

later before your first access.  Python's list.sort() realizes if a list is
"sorted at the start, and then has 'some small amount of' disordered gunk at
the end", and in that case does a fast sequence of binary inserts under
covers to clean up the gunk.  Yet this is still a disaster if priority
queues get very large.

A much better way to do priority queues if they can get large is via a heap.
Then insertion, deletion and lookup never take worse than O(log(n)) time.

Finally, note that the std module random has a random.shuffle function.

luckily-the-python-libraries-are-much-smaller-than-java's-so-it's-
    possible-to-learn-all-of-them-in-less-than-a-decade<wink>-ly y'rs
    - tim