DALPy-Developers/DALPy

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.