I am using a priority_queue-s for implementing A* and Dijkstra's algorithm. Is there a point writing my own heap for time optimization? How faster would it be? I read in wikipedia that Fibonacci heap will be the best. Do you agree?
The_Purple_Mask 0 Newbie Poster
deceptikon 1,790 Code Sniper Team Colleague Featured Poster
Is there a point writing my own heap for time optimization?
It's pretty unlikely that an ad hoc heap would be faster than std::priority_queue. Not to mention the effort of reinventing the wheel *and* the huge risk of bugs in your implementation that just aren't there with an existing oft used library.
Ask yourself if the potential speed improvements are worth the effort and risks. In my experience, the choice is nearly always to use the existing library instead of writing your own.
jaskij 45 Junior Poster in Training
Also, a word of warning if you are using MS Visual Studio:
VS has a lot of runtime checks built in their debug implementation of STL, so if you run it under debug it will most likely feel terribly slow.
In my case it came out when I wrote a simple app to render Mandelbrot and Julia sets. The difference was immense. In debug, it would take a fair amount of time to render with around 16 iterations, while in release it would be faster even at around 60-70 iterations.
mike_2000_17 2,669 21st Century Viking Team Colleague Featured Poster
The main problem you will have with STL's priority-queue is not the efficiency, but the fact that it provides no means to update the priority value of elements already in the queue. This is an operation that is required in A* (at least, the last time I checked).
If you take a look at the Boost.Graph Library's implementations of A* and Dijkstra, which both are just thin-wrappers for a Breadth-first visitation algorithm, use a custom priority-queue implementation. This priority-queue is called d_ary_heap_indirect which is a D-ary heap implementation with an indirect priority value, but most importantly, it includes the necessary update() and push_or_update() functions that STL's priority-queue lacks.
The STL's priority-queue will be faster for more simple operations (just pushing and popping) because it is a relaxed heap (giving constant-time pushing). But, for more dynamic operations, I recommend BGL's d_ary_heap_indirect implementation. Better, yet, you could just use the BGL's A* and Dijkstra implementations.
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.