在最小堆与标准:: priority_queue推动是瓶颈(Pushing in min heap

东西比更快std::priority_queue为最小堆？

原来的问题是在这里。您可以通过解析与grpof所产生的名字demangler 。随着用户那里的帮助下，我得出一个结论，其中（得到执行，我期待更多的时间比我将执行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));
  }
}

似乎是我的项目（我认为），因为我可以调用此之后看到的瓶颈：

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

而得到这个：

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]

我推的方式更多的项目比我弹出。在这个问题我联系我表明，相对于我的堆的代码。我们可以假设，堆永远不会空。我不知道有关的分布。

参见维基堆比较：

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

你可以得到最快的是斐波那契堆。 AFAIK STL的优先级队列仅仅是一个二元堆。你可以通过提高速度提升斐波那契堆实现。而且，这里是一个问题，从SO显示升压堆的使用情况。

值得一提的事情是，在维基百科显示的数据是堆的理论比较。 STL的实现是二进制堆，因为它通常是快得多然后斐波那契堆为小尺寸的堆。漂亮的问题，总结斐波那契堆信息是在这里。