2

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.

Improve this question
10
  • 1
    The heapq documentation (docs.python.org/3.5/library/heapq.html) doesn't seem to mention the index method at all. How many keys are you passing in wKeys? In general, I wouldn't expect finding the index of a specific member would be fast - though my comp sci is pretty rusty. Ref docs.python.org/3.5/library/… it seems that "how do you find [an item] and remove it from the queue?" is an open problem, though it suggests a solution there. I think in general what you want to do isn't a 'built-in' property of a binary heap. Commented Mar 5, 2018 at 16:15
  • 1
    A binary tree just means that each node has at most 2 children. A binary tree in itself has no innate 'ordering' on the nodes. It just so happens that a common use of binary trees is an ordered binary tree that allows efficient binary search. It's possible that treap has some additional implementation (such as the 'addon' dictionary) that makes lookup efficient, but that will come at the code of additional operations on push/pop and additional storage cost. Commented Mar 5, 2018 at 16:59
  • 1
    @EndreMoen: The binary heap is organized as a binary tree, but not a binary search tree. Finding an item in a binary heap requires a sequential search. Commented Mar 5, 2018 at 16:59
  • 2
    Removing an arbitrary element from a binary heap is an O(log n) operation, as described in stackoverflow.com/a/8706363/56778. Finding an arbitrary element is an O(n) operation, unless you combine the heap with a lookup mechanism like a hash map or dictionary that keeps track of each item's location in the heap. Commented Mar 5, 2018 at 17:06
  • 1
    You need to modify the heap code so that it includes a dictionary that has the item key as the key, and the item's index in the heap as the value. In the code that moves items, you have to update the item's position in the dictionary every time you move the item in the heap. There are probably examples of doing that in python. If not, it's not a difficult modification. Commented Mar 5, 2018 at 17:27

2 Answers 2

Reset to default
1

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 :)

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

added changeValue()
heappop_arbitrary() and changeValue() are still quite slow.
heappop_arbitrary() and changeValue() shouldn't be slow. They should be faster than heappop2(). Also, you should be able to re-code your else: (the last one) in heappop_arbitrary' to remove the last item from the heap and then call changeValue()`.
0 
class RemoveHeap:
    def __init__(self):
        self.h = []
        self.track = collections.defaultdict(collections.deque)
        self.counter = itertools.count()

    def insert_item(self, val):
        count = next(self.counter)
        item = [val, count, 'active']
        self.track[val].append(item)
        heapq.heappush(self.h, item)

    def delete_item(self, val):
        if val in self.track:
            items = self.track[val]
            for item in items:
                if item[2] == 'active':
                    item[2] = 'deleted'
                    break

    def pop_item(self):
        while len(self.h) > 0:
            item = heapq.heappop(self.h)
            item_track = self.track[item[0]]
            item_track.popleft()
            if len(item_track) == 0:
                del self.track[item[0]]
            else:
                self.track[item[0]] = item_track
            if item[2] == 'active':
                return item[0]

    def peek_item(self):
        item = self.h[0]
        if item[2] == 'deleted':
            x = self.pop_item()
            self.insert_item(x)
            return x
        return item[0]
Improve this answer

1 Comment

Have you tried heapq_with_index that I linked to in answere below?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.