c++ - std::heap __adjust_heap函数如何工作？

我正在使用std::priority_queue，并且试图了解pop函数的工作原理以了解每个pop调用中发生了多少比较。我已经看到优先级队列基于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));
}

最佳答案

该标准指定比较次数最多为log(N)，其中N是堆的大小。

参见例如http://en.cppreference.com/w/cpp/algorithm/push_heap

您列出的帮助程序功能仅是实现细节(如您从__的主要名称中所见)

关于c++ - std::heap __adjust_heap函数如何工作？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/46281798/