how does the std::heap __adjust_heap function work?

Question

I am using the std::priority_queue and I'm trying to understand how does the pop function works to know how many compares occurs in every pop call. I have seen that the priority queue is based on the std::heap. Specifically, the pop function is using the __adjust_heap function. I have tried to understand this function but I encountered difficulties with the logic part.

I know that in the standard pop_heap function the top object is removed and then the last one is taken to the top and being compared with its two children. but in this code it seems not to be the case.

can someone help me understand how does it work here?

__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));
}

Formatting for more readability:

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

The standard specifies that the number of comparisons shall be at most log(N) where N is the size of the heap.

See e.g. http://en.cppreference.com/w/cpp/algorithm/push_heap

The helper function you list is an implementation detail only (as you can see from the __ leading name)

Answer 2

I haven't analyzed the function in detail, but I have found a short description of it in this book, page 201:

"Template function Adjust_heap percolates a hole down the heap until it has no children. It then calls Push_heap to percolate the hole back up the heap to the proper place to store the specified value. Adjust_heap is called from template function Partial_sort_copy and from several places among the heap template functions."