Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #101375

Re: How to remove item from heap efficiently?

Show all headers | View raw

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.

Back to comp.lang.python | Previous | Next | Find similar | Unroll thread

Thread

Re: How to remove item from heap efficiently? Peter Otten <__peter__@web.de> - 2016-01-08 14:26 +0100

csiph-web