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 -- http://mail.python.org/mailman/listinfo/python-list
