[Python-Dev] collections.sortedtree

[Antoine Pitrou]

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.