Pushing in min heap with std::priority_queue is th

Question

Something faster than std::priority_queue as a min heap?

---

The original question is here. You can resolve the names generated by grpof with the demangler. With the help of the users there, I came to a conclusion, where this block of code (that I expect to get executed much more times than I will perform a pop):

/**
 * 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;
...
void nn(..) { // the core function of my project
  if(...) {
    branch.push(std::make_tuple(new_dist, other_child_i, tree_i));
  }
}

seems to be the bottleneck of my project (I think), as I can see after calling this:

gprof -q_ZN3RKDI24Division_Euclidean_spaceIfEE2nnEjRKSt6vectorIfSaIfEERKfRS3_ISt4pairI‌​fiESaISB_EERiiPjRSt14priority_queueISt5tupleIJfiiEES3_ISJ_SaISJ_EESt7greaterISJ_E‌​ES9_RKjS7_S7_i geraf gmon.out > analysis.txt

and got this:

granularity: each sample hit covers 2 byte(s) for 0.01% of 125.47 seconds

index % time    self  children    called     name
                             1967195             _ZN3RKDI24Division_Euclidean_spaceIfEE2nnEjRKSt6vectorIfSaIfEERKfRS3_ISt4pairIfiESaISB_EERiiPjRSt14priority_queueISt5tupleIJfiiEES3_ISJ_SaISJ_EESt7greaterISJ_EES9_RKjS7_S7_i [2]
              105.54    0.09  320000/320000      Auto_random_kd_forest<float>::Auto_random_kd_forest(unsigned int&, unsigned int&, std::string const&, unsigned int, std::string const&, int, float, std::vector<std::vector<std::pair<float, int>, std::allocator<std::pair<float, int> > >, std::allocator<std::vector<std::pair<float, int>, std::allocator<std::pair<float, int> > > > >&, Params*, int) (1)
[2]     84.2  105.54    0.09  320000+1967195 _ZN3RKDI24Division_Euclidean_spaceIfEE2nnEjRKSt6vectorIfSaIfEERKfRS3_ISt4pairIfiESaISB_EERiiPjRSt14priority_queueISt5tupleIJfiiEES3_ISJ_SaISJ_EESt7greaterISJ_EES9_RKjS7_S7_i [2]
                0.08    0.00 1967195/2031195     void std::__push_heap<__gnu_cxx::__normal_iterator<std::tuple<float, int, int>*, std::vector<std::tuple<float, int, int>, std::allocator<std::tuple<float, int, int> > > >, int, std::tuple<float, int, int>, std::greater<std::tuple<float, int, int> > >(__gnu_cxx::__normal_iterator<std::tuple<float, int, int>*, std::vector<std::tuple<float, int, int>, std::allocator<std::tuple<float, int, int> > > >, int, int, std::tuple<float, int, int>, std::greater<std::tuple<float, int, int> >) [9]
                0.01    0.00   12000/12000       _ZNSt6vectorISt5tupleIJfiiEESaIS1_EE19_M_emplace_back_auxIJS1_EEEvDpOT_ [11]
                             1967195             _ZN3RKDI24Division_Euclidean_spaceIfEE2nnEjRKSt6vectorIfSaIfEERKfRS3_ISt4pairIfiESaISB_EERiiPjRSt14priority_queueISt5tupleIJfiiEES3_ISJ_SaISJ_EESt7greaterISJ_EES9_RKjS7_S7_i [2]
-----------------------------------------------
                0.00    0.00   64000/2031195     _ZSt13__adjust_heapIN9__gnu_cxx17__normal_iteratorIPSt5tupleIJfiiEESt6vectorIS3_SaIS3_EEEEiS3_St7greaterIS3_EEvT_T0_SC_T1_T2_ (10)
                0.08    0.00 1967195/2031195     _ZN3RKDI24Division_Euclidean_spaceIfEE2nnEjRKSt6vectorIfSaIfEERKfRS3_ISt4pairIfiESaISB_EERiiPjRSt14priority_queueISt5tupleIJfiiEES3_ISJ_SaISJ_EESt7greaterISJ_EES9_RKjS7_S7_i [2]
[9]      0.1    0.09    0.00 2031195         void std::__push_heap<__gnu_cxx::__normal_iterator<std::tuple<float, int, int>*, std::vector<std::tuple<float, int, int>, std::allocator<std::tuple<float, int, int> > > >, int, std::tuple<float, int, int>, std::greater<std::tuple<float, int, int> > >(__gnu_cxx::__normal_iterator<std::tuple<float, int, int>*, std::vector<std::tuple<float, int, int>, std::allocator<std::tuple<float, int, int> > > >, int, int, std::tuple<float, int, int>, std::greater<std::tuple<float, int, int> >) [9]
-----------------------------------------------
                0.01    0.00   12000/12000       _ZN3RKDI24Division_Euclidean_spaceIfEE2nnEjRKSt6vectorIfSaIfEERKfRS3_ISt4pairIfiESaISB_EERiiPjRSt14priority_queueISt5tupleIJfiiEES3_ISJ_SaISJ_EESt7greaterISJ_EES9_RKjS7_S7_i [2]
[11]     0.0    0.01    0.00   12000         _ZNSt6vectorISt5tupleIJfiiEESaIS1_EE19_M_emplace_back_auxIJS1_EEEvDpOT_ [11]

---

I am pushing way more items than I pop. In the question I linked I show the code that is relative with my heap. We can assume that the heap never gets empty. I am not sure about the distribution.

Answer 1

See the heap comparison on the wiki:

http://en.wikipedia.org/wiki/Heap_(data_structure)

The fastest you can get is Fibonacci heap. AFAIK the STL priority queue is just a binary heap. You could improve on speed by using the boost implementation of the fibonacci heap. Also here is a question from SO showing the usage of the boost heap.

The thing worth mentioning is that the data shown in the wikipedia is theoretical comparison of heaps. The STL implementation is the binary heap because it is usually much faster then fibonacci heap for heaps of small size. The nice question summarising the fibonacci heap information is here.