Prakhar - 3 months ago 47

Python Question

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

heapq.heapify(h)

break

Answer

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.

**UPDATED:**

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.

Source (Stackoverflow)

Comments