How to remove item from heap efficiently?
Peter Otten
__peter__ at web.de
Fri Jan 8 08:26:28 EST 2016
Sven R. Kunze wrote:
> Hi everybody,
>
> 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?
The heapq docs mention marking as deleted as an alternative to removing.
Another option is to try sorted lists and bisect.
More information about the Python-list
mailing list