std :: heap __adjust_heap関数はどのように機能しますか？

Question

私はstd :: priority_queueを使用しています。ポップアップ関数がどのように多くの比較がすべてのポップコールで発生するかを知るためにどのように機能するのか理解しようとしています。優先キューはstd :: heapに基づいていることがわかりました。具体的には、pop関数は__adjust_heap関数を使用しています。私はこの機能を理解しようとしましたが、ロジック部分に問題が発生しました。

私は、標準のpop_heap関数では、上のオブジェクトが削除され、最後のオブジェクトが上に移動して2つの子と比較されることが分かります。しかし、このコードではそうではないようです。

ここでどのように動作するのか理解できますか？

__adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex, 
     _Distance __len, _Tp __value, _Compare __comp) 
{ 
    const _Distance __topIndex = __holeIndex; 
    _Distance __secondChild = __holeIndex; 
    while (__secondChild < (__len - 1)/2) 
{ 
    __secondChild = 2 * (__secondChild + 1); 
    if (__comp(__first + __secondChild, 
     __first + (__secondChild - 1))) 
    __secondChild--; 
    *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild)); 
    __holeIndex = __secondChild; 
} 
    if ((__len & 1) == 0 && __secondChild == (__len - 2)/2) 
{ 
    __secondChild = 2 * (__secondChild + 1); 
    *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first 
         + (__secondChild - 1))); 
    __holeIndex = __secondChild - 1; 
} 
    std::__push_heap(__first, __holeIndex, __topIndex, 
      _GLIBCXX_MOVE(__value), 
      __gnu_cxx::__ops::__iter_comp_val(__comp)); 
} 

より読みやすくするためのフォーマット：

adjust_heap(RandomAccessIterator first, Distance holeIndex, Distance len, Tp value, Compare comp) { 
    const Distance topIndex = holeIndex; 

    Distance secondChild = holeIndex; 

    while (secondChild < (len - 1)/2) { 
     secondChild = 2 * (secondChild + 1); 
     if (comp(first + secondChild, first + (secondChild - 1))) 
      secondChild--; 
     *(first + holeIndex) = std::move(*(first + secondChild)); 
     holeIndex = secondChild; 
    } 

    if ((len & 1) == 0 && secondChild == (len - 2)/2) { 
     secondChild = 2 * (secondChild + 1); 
     *(first + holeIndex) = std::move(*(first + (secondChild - 1))); 
     holeIndex = secondChild - 1; 
    } 

    std::push_heap(first, holeIndex, topIndex, std::move(value), gnu_cxx::ops::iter_comp_val(comp)); 
} 

Answer 1

標準は、比較の数は、ほとんどのログNは、ヒープのサイズです（N）にしなければならないことを指定します。

http://en.cppreference.com/w/cpp/algorithm/push_heap

ヘルパー関数あなたリストは（あなたが__一流の名前から見ることができるように）