std :: heap __adjust_heap函數是如何工作的？

Question

我正在使用std :: priority_queue，我試圖理解彈出函數如何工作以知道在每次彈出窗口調用中會發生多少次比較。我已經看到，優先隊列是基於std :: heap的。具體來說，pop函數使用__adjust_heap函數。我試圖理解這個功能，但是我遇到了邏輯部分的困難。

我知道，在標準的pop_heap函數中，頂層對象被刪除，然後最後一個被帶到頂端並與其兩個孩子進行比較。但在此代碼中似乎並非如此。

有人能幫我理解它在這裏如何工作？

__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

您列出輔助功能僅實現細節（因爲你可以從__領先的名字就能看出）