Actually, after posting this I did some more work on the PQueue modules I had, implementing both bisect and heapq versions. It turns out the bisect version is heaps faster if you ever delete or re-set values in the queue.
The problem is heapq is O(N) for finding a particular entry in the Queue, and any time you change or remove something from it you need to heapify it again, which is also O(N). Andew Snare has a C PQueue extension module that is heaps faster from all angles. It uses a fibonacci heap and gets O(lg N) deletes and re-sets. I think it does this by using the dict to speed finding entries it in the heap, and uses some properties of the heap to "assign lower" efficiently. The queue used in the lrucache will also suffer from the O(N) problem when deleting or reseting values in the cache. -- http://mail.python.org/mailman/listinfo/python-list