[SOLVED] delete arbitrary item from heap in python

delete arbitrary item from heap in python

Is there a binary heap implementation where I can pop other elements than the root in log n time?

I use heapq - but heap.index( wKeys ) in

heap.pop( heap.index( wKeys ) )

is very slow. I need a binary heap for my problem - where I sometime use

heapq.heappop(heap)

but also need to pop other elements than at the top from the heap. So a binary heap like heapq imlementation should do that but I havnt found a binary search method. I also looked at treap (http://stromberg.dnsalias.org/~strombrg/treap/) and cannot find a method like this here either.

Solution

Ive modified the implementation of heapq by adding a parameter to heappop(), and heappush() - which is heapIndex. That takes a dictionary of {item: index} and updates the heapIndex as it pops or pushes into heap.

Ive also added a new method heappop_arbitrary() which deletes an arbitrary element and updates the heapIndex

The code is available here: https://github.com/emoen/heapq_with_index

Ive renamed the methods heappop(),heappush() to heappop2(), heappush2() to avoid confusion with the original methods.

I havent implemented this for any of the other functions available in heapq.

Edit: please star if you can use the repo :)