Heap Queues are extremely useful data structures. They can, for example, be used to implement Dijkstra's algorithm for finding the shortest paths between nodes in a graph in O(edge * log vertices) time instead of (edge * vertices) without heaps.

One operation such implementations need, though, is the possibility to modify an element in the heap (and thus having to reorder it afterwards) in O(log n) time. One can model such an operation by removing a specific element from the heap and then adding the modified element.

So far, heapq only allows removing the first element through heappop; this is not what we need. Instead, we would want to support a heapremove function that removes an arbitrary element in the heap (if it exists) and raises ValueError if the value is not present.

list.remove cannot be used, since it needs O(n) time.

heapremove can be easily implemented by using bisect.bisect_left since heap is always sorted:

def heapremove(heap, x):
  i = bisect.bisect_left(heap, x)
  if heap[i] == x:
    del heap[i]
  else:
    raise ValueError

c.f. remove method in https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html

After thinking about it some more I realised that this doesn't make sense since heapq is based on lists and lists have an insertion complexity of O(n). Thus, they'll never read the needed O(log n) and heapq is the wrong place.

Never mind.

For history, note that `bisect` doesn't always work in this context either:  a heap is NOT always in sorted order.  For example, this is "a (min) heap" too:  [1, 3, 2].

More, that's "the real" problem.  If we could find the element to be removed in log(n) time, then it's possible to remove it from the heap in log(n) time too (you can, e.g., bubble elements up to fill the interior hole, then move the last heap element into the leaf hole that may leave behind and possibly sift it up to restore the heap property; and each of those phases takes log(n) time).