[Python-Dev] collections.sortedtree
Antoine Pitrou
solipsis at pitrou.net
Thu Mar 27 16:53:15 CET 2014
On Thu, 27 Mar 2014 08:50:01 -0700
Daniel Stutzbach <stutzbach at google.com> wrote:
>
> Due to way the heapq is implemented, it can't provide an efficient API for
> removing an arbitrary item. Swapping with the last element allows you to
> efficiently remove the item at a particular index, but you first need to
> find the current index of an item, which requires a O(n) scan.
>
> To provide efficient cancellation and removal, a heap implementation needs
> some way to efficiently answer "What is the current index of this item?".
> There are a couple of ways to achieve that, but they all require more
> storage than heapq's list-based approach.
You are right. I was assuming the index is already known.
Regards
Antoine.
More information about the Python-Dev
mailing list