swift-collections icon indicating copy to clipboard operation
swift-collections copied to clipboard

Consider adding an indexed heap

Open dabrahams opened this issue 1 year ago • 0 comments

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.

dabrahams avatar Dec 24 '24 19:12 dabrahams