Fix misaligned PriorityQueue runtimes
EitanJoseph opened this issue · 1 comments
Is your feature request related to a problem? Please describe.
Currently, PriorityQueue
is backed by a sorted list. Therefore, the actual runtimes of DALPy PriorityQueue
functions is misaligned with their assumed runtimes.
Describe the solution you'd like
PriorityQueue
should be reimplemented using Python's base library heapq
with a custom decrease_key
function that mantains O(log(n)) runtime.
In order to maintain decrease_key
functionality, it turned out heapq
could not be used (even for the other operations). This is due to the fact that any table that tracks elements in the heap would have to be updated by any operation that updates the heap (including heapq
's push and pop). Therefore, PriorityQueue
had to be reimplemented from scratch.
An alternative that would still use heapq
would mark items adjusted with decrease_key
as invalid and then add a new copy of that item. However, I believe this would lead to worse runtime, especially if an item's key is adjusted many times (e.g. Dijkstra's, Prim's). See more on this alternative here.