swift-collections
swift-collections copied to clipboard
Consider adding an indexed heap
An indexed heap is required for a traditional implementation of Dijkstra's shortest paths algorithm. It adds a DECREASE-KEY operation that optimally alters the priority of an existing element in the queue in O(log N) time. Perhaps worth taking this request with a grain of salt as some benchmarks seem to show using a standard heap is faster, though it has poor worst-cast space complexity. Also I have an optimization of the standard heap approach here that might change the calculus.