heap __adjust_heap函数是如何工作的？

Question

我正在使用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));
}

Answer 1

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

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

您列出的帮助器函数只是一个实现细节(从__前导名称中可以看到)

Answer 2

我还没有详细分析这个函数，但我在this book的第201页找到了它的简短描述：

“模板函数Adjust_heap在堆中向下渗透一个洞，直到它没有子代。然后它调用Push_heap将该洞沿堆向上渗透到存储指定值的适当位置。从模板函数Partial_sort_copy和堆模板函数中的几个位置调用Adjust_heap。”

Answer 3

您没有提到代码是从哪里截取的，但我假设它来自于C++标准库的某个实现(例如，可以在here中找到的gcc libc++ )。

该函数将二进制堆中的一个元素向下移动到最底部，然后调用push_heap将其再次向上移动，直到恢复了max-heap属性(每个元素的子元素的值小于元素本身的值)。

为什么元素被推到最底部，然后又被抬起来呢？为什么我们不在元素到达它的最终目的地后停止呢？这个问题的答案可能在于adjust_heap函数的典型用法。它用在pop_heap函数中，该函数将根节点(我们想要提取或“弹出”的那个)与最右边的叶子交换，然后使用adjust_heap向下接收新的根节点，直到恢复堆属性。如果我们想要在元素到达其最终位置时立即停止，我们需要每个下降步骤进行2次比较(比较两个孩子，以确定我们必须下降的方向，并与元素进行比较，以确定我们是否需要停止)。这些比较中的第二个可以通过首先向下一直下降，然后再次向上移动元素来保存。如果元素的最终位置接近底部(很可能是这样，因为新的根最初来自最右边的叶子)，则操作速度可以比传统的“下降到到达最终位置”更快。

例如，堆排序的Bottom-up变体中也使用了这种先向下移动，然后再向上移动的方法。