[New-bugs-announce] [issue35659] Add heapremove() function to heapq

[Wanja Chresta]

New submission from Wanja Chresta <wanja.chresta at gmail.com>:

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

----------
components: Library (Lib)
messages: 333024
nosy: Wanja Chresta
priority: normal
severity: normal
status: open
title: Add heapremove() function to heapq
versions: Python 3.8

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue35659>
_______________________________________