Path: csiph.com!fu-berlin.de!uni-berlin.de!not-for-mail
From: Oscar Benjamin <oscar.j.benjamin@gmail.com>
Newsgroups: comp.lang.python
Subject: Re: How to remove item from heap efficiently?
Date: Thu, 14 Jan 2016 11:53:52 +0000
Lines: 30
Message-ID: <mailman.144.1452772455.13488.python-list@python.org>
References: <568EEC40.7070807@mail.de>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8
In-Reply-To: <568EEC40.7070807@mail.de>
Precedence: list
Xref: csiph.com comp.lang.python:101684

On 7 January 2016 at 22:52, Sven R. Kunze <srkunze@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