Required Skills: C++

Difficulty: Hard

openage provides a pairing heap implementation that is mostly used in the A* algorithm of our pathfinder. Currently, nodes on the heap are connected using shared_ptr. However, we have noticed that the creation of shared_ptr objects when using the heap is very slow. A variant with raw pointers and without shared_ptr may offer better performance benefits.

A previous implementation already used raw pointers. You can see it in commit 4ab602a

Tasks:

• Implement the pairing heap without using shared_ptr or enable_shared_from_this. You can use the implemenation in 4ab602a as a reference but be aware that other parts of the code may have changed since then.
• Use callgrind to compare the speed of the old implementation with your solution that uses precomputed graphs:

valgrind --tool=callgrind ./run test -d pathfinding.tests.path_demo 1

Further Reading

• pairing heap code