how does the std::heap __adjust_heap function work?

user_8088008 0
Viewed 1049

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));
}
c++11 c++
3 Answers

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."

user_49689630

You did not mention where you got the code snipped from, but I assume, that it is from some implementation of the C++ standard library (like e.g. the gcc libc++ , which can be found for example here).

The function moves an element in the binary heap down to the very bottom, and then calls push_heap to move it upwards again until the max-heap property is restored (the values of each element's children are smaller than the value of the element itself).

Why is the element is pushed down to the very bottom and than raised again? Why do we not just stop after the element reached its final destination? Probably the answer to that question lays in the typical usage of the adjust_heap function. It is used in the pop_heap function, which swaps the root node (the one, that we want to extract or "pop") with the rightmost leaf, and then uses adjust_heap to sink the new root downwards until the heap property is restored. If we want to stop immediately if the element reaches its final place, we need 2 comparisons per descend step (compare both the children, to determine in which direction we have to descend and compare to the element, to determine if we need to stop). The second of these comparisons can be saved by first descending all the way down and then move the element up again. If the element's final place is near the bottom, (which it most likely is, because the new root came from the rightmost leaf in the first place), the operation can be faster than the traditional "descend until final place reached".

This method of first moving all the way down and then moving up again is for example also used in the Bottom-up variant of heapsort.

user_178623710
Related