Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Consider adding an indexed heap #442

Open
dabrahams opened this issue Dec 24, 2024 · 0 comments
Open

Consider adding an indexed heap #442

dabrahams opened this issue Dec 24, 2024 · 0 comments
Labels
enhancement New feature or request

Comments

@dabrahams
Copy link

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 dabrahams added the enhancement New feature or request label Dec 24, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request
Projects
None yet
Development

No branches or pull requests

1 participant