Code for Game Developers - Heaps

We want to speed up Dijkstra's Algorithm by avoiding the linear O(n) scan through all unvisited notes. To do this we put our nodes in a heap, which allows us to always quickly access the fastest node.

[ttrkaya]

Thank you very much for this great tutorial. 

Something bothers me about your algorithm. Yes we have decreased the complexity of finding the minimum distance node from O(n) to O(logn) and this is great.

But we could have updated the neighbor nodes each at O(logn) too. It would be a huge speed-up if the graph is sparse, which in many cases like games, it is.

make_heap function is O(n) and your overall complexity is still O(n^2), for sparse graphs we can achieve O(nlogn). A significant improvement.

I am searching for a way to implement my O(nlogn) version of algorithm, if I manage to pull it off, I will share here.

[orkhanalikhanov]

What about using priority_queue to sort our stuff continuously there.

as implemented here.