Alternative title:
Implement min heap with something faster than std::priority_queue.
grpof gave me:
time seconds seconds calls s/call s/call name
84.12 105.54 105.54 320000 0.00 0.00 _ZN3RKDI24Division_Euclidean_spaceIfEE2nnEjRKSt6vectorIfSaIfEERKfRS3_ISt4pairIfiESaISB_EERiiPjRSt14priority_queueISt5tupleIJfiiEES3_ISJ_SaISJ_EESt7greaterISJ_EES9_RKjS7_S7_i
which I believe is my only std::priority_queue used in the project. The 'Division_Euclidean_space' part confuses me, since it's a class/file not used any more in my project.
Here is what I use exactly:
/**
* Min_heap is actually a std::priority_queue,
* with std::greater as a parameter.
*/
typedef std::priority_queue<std::tuple<float, int, int>,
std::vector<std::tuple<float, int, int> >,
std::greater<std::tuple<float, int, int> > > Min_heap;
I use the first element as the key for comparison.
and as one can see in my repo, I create only one Min_heap and I use it in two parts:
if(...) {
branch.push(std::make_tuple(new_dist, other_child_i, tree_i));
}
and
while (branch.size()) {
std::tie(new_mindist, node_i, tree_i) = branch.top();
branch.pop();
...
}
I feel that if I replace this data structure with something else, my project may run a bit faster (super duper great). Any ideas?
I push items in the heap for a while, then I pop one and I will probably push other items do and so on. Most of the times I stop with another condition, not when the heap gets empty.
