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

Groups > comp.lang.python > #101404

Re: How to remove item from heap efficiently?

Show key headers only | View raw

Thanks for your reply.

On 08.01.2016 14:26, Peter Otten wrote:
> 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.
That is how I do it for now. However, the heap continues to grow which 
needs a periodic clean up.
> Another option is to try sorted lists and bisect.
The docs tell me that insertion is not really fast then. :/


Best,
Sven

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

Thread

Re: How to remove item from heap efficiently? "Sven R. Kunze" <srkunze@mail.de> - 2016-01-08 17:52 +0100

csiph-web