Prakhar Prakhar - 11 months ago 151
Python Question

Deleting from python heapq in O(logn)

I have a heap (python, heapq module) like this -

>>> h = []
>>> heappush(h, (5, 'write code'))
>>> heappush(h, (7, 'release product'))
>>> heappush(h, (1, 'write spec'))
>>> heappush(h, (3, 'create tests'))

How do I remove the tuple with item value as "create tests" in O(logn) and preserve the heap property?

This is what I could come up with (not O(logn))

for i in range(len(h)):
if h[i][1] == "create tests":
h[i], h[-1] = h[-1], h[i]
popped = h.pop()

Answer Source

I'm afraid there's no such method with heapq only. Since searching an element from a heap requires O(n).

But you can use it together with something like dict, which gives O(1) time for searching an entry.


I tried using a dict for bookkeeping, but how can I get the index of "create test" when it was inserted? – Prakhar 3 hours ago

A naive approach would be:

# remember to update this hdict when updating the heap.
hdict = { h[i][1]: i for i in range(len(h)) }

Then you can just obtain index of a given string by accessing this hdict instead of your O(n) linear search.