RetroSearch Browse

Thu Mar 27 16:53:15 CET 2014 · http://mail.python.org/pipermail/python-dev/2014-March/133592.html

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.

Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Showing content from http://mail.python.org/pipermail/python-dev/2014-March/133592.html below:

[Python-Dev] collections.sortedtree