New submission from Wanja Chresta <wanja.chre...@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 <rep...@bugs.python.org>
<https://bugs.python.org/issue35659>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe:
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
