On benchmarks, heaps, priority queues

[Szabolcs Nagy]

hello
nice benchmarks

some time ago i've also done some benchmarking
i sorted 100000 random int with differrent heap implementations, bisect
module and with list.sort()
I know that heaps are not for sorting, but i tested their performance
with sorting back then.

my results (sorting algo / time):

myheap: (my dummy heap implementation with non-standard comparison)
4.08311503909
heapdict: (my heapdict able to update/delete arbitrary items:
heap[key]=value)
5.11007613686
priodict:
(http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/117228)
4.96804296435
pyheapq: (heapq from py 2.3)
2.37830548956
cheapq:  (heapq from py 2.4)
0.375011378197
sort:  (list.sort)
0.118014529543
bisect:  (bisect module)
3.88104577077

i didn't made many benchmarks
but bisect is not so fast with larger amount of data (if i saw well
your PQ0 implementation used bisect)
it's not scaleable (not even O(nlog(n)) !!!!  because inserting in a
python list is not O(1))
however for small amount of data bisect is the fastest

if i used 10 times more data every algorithm scaled well except for
bisect:

myheap:
50.6242882263
heapdict:
67.465409454
priodict:
71.5018580555
pyheapq:
30.9821771082
cheapq:
6.41072844834
sort:
1.58179548464
bisect:
785.215063469

nsz