a heap with decrease-key and increase-key operations
heapdict implements the MutableMapping ABC, meaning it works pretty much like a regular Python dict. It’s designed to be used as a priority queue, where items are added and consumed as follows:
hd = heapdict() hd[obj1] = priority1 hd[obj2] = priority2 # ... obj = hd.pop()
Compared to an ordinary dict, a heapdict has the following differences:
Unlike the Python standard library’s heapq module, the heapdict supports efficiently changing the priority of an existing object (often called “decrease-key” in textbooks). Altering the priority is important for many algorithms such as Dijkstra’s Algorithm and A*.