On 7 January 2016 at 22:52, Sven R. Kunze <srku...@mail.de> wrote: > > suppose, I need items sorted by two criteria (say timestamp and priority). > For that purpose, I use two heaps (heapq module): > > heapA # items sorted by timestamp > heapB # items sorted by priority > > Now my actual problem. When popping an item of heapA (that's the oldest > item), I need to remove the very same item from heapB, regardlessly where it > is in heapB. And vice versa. > > Is there a datastructure or a simple trick to achieve that in an efficient > matter?
Essentially you want a data structure that can efficiently do the following: 1) add an arbitrary item 2) remove an arbitrary item 3) get/pop the minimum element So Python's set object does add/remove in O(1) but min in O(N). A heap does add and min in O(log(N)) but remove in O(N). Self-balancing binary trees can do all of add/remove/min in O(log(N)) so I guess that's better than what you currently have. Google shows many third party implementations for Python. Here's one: https://pypi.python.org/pypi/bintrees/2.0.2 -- Oscar -- https://mail.python.org/mailman/listinfo/python-list
