我查看了C ++ 0x标准，发现要求make_heap最多只能进行3 * N个比较。
即堆一个无序集合可以在O（N）中完成
/* @brief Construct a heap over a range using comparison functor.
为什么是这样？
资料来源没有任何提示（g ++ 4.4.3）
while（true）+ __parent == 0不是线索，而是对O（N）行为的猜测
template<typename _RandomAccessIterator, typename _Compare> void make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { const _DistanceType __len = __last - __first; _DistanceType __parent = (__len - 2) / 2; while (true) { _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent)); std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value), __comp); if (__parent == 0) return; __parent--; } }
__adjust_heap看起来像一个log N方法：
while ( __secondChild < (__len - 1) / 2) { __secondChild = 2 * (__secondChild + 1);
对我来说是沼泽标准日志N。
template<typename _RandomAccessIterator, typename _Distance, typename _Tp, typename _Compare> void __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), __comp); }
为什么这是O <= 3N的任何线索将不胜感激。 编辑：
实验结果：
该实际实现使用
使用聪明的算法和聪明的分析，可以在O（n）时间内创建n个元素上的二进制堆。在接下来的内容中，我将假设您具有显式节点以及显式左右子指针，然后再讨论它的工作原理，但是一旦将其压缩到数组中，此分析仍然是完全有效的。
该算法的工作原理如下。首先，获取大约一半的节点并将其视为单例最大堆- 由于只有一个元素，因此仅包含该元素的树必须自动成为最大堆。现在，摘下这些树并将它们彼此配对。对于每对树，请使用尚未使用的值之一并执行以下算法：
使新节点成为堆的根，使其左，右子指针指向两个最大堆。
当此节点的子节点大于它的子节点时，请将该子节点与其较大的子节点交换。
我的主张是，此过程最终产生了一个新的最大堆，其中包含两个输入的最大堆的元素，并且它的执行时间为O（h），其中h是两个堆的高度。证明是对堆高的归纳。作为基本情况，如果子堆的大小为零，则该算法立即以单例最大堆终止，并且在O（1）时间内终止。对于归纳步骤，假设对于某个h而言，此过程适用于任何大小为h的子堆，并考虑在两个大小为h + 1的堆上执行它时会发生什么情况。当我们添加新的根将两个大小为子的子树连接在一起时h + 1，有三种可能性：
新的根大于两个子树的根。然后，在这种情况下，我们有了一个新的max-heap，因为根大于任一子树中的任何节点（根据传递性）
新的根大于一个孩子，而小于另一个孩子。然后，我们将根与较大的子子项交换，并再次使用旧的根和子项的两个子树递归地执行此过程，每个子树的高度均为h。根据归纳假设，这意味着我们交换到的子树现在是最大堆。因此，总堆是最大堆，因为新的根大于我们交换的子树中的所有内容（因为它大于我们添加的节点，并且已经大于该子树中的所有内容），并且也大于所有内容在另一个子树中（因为它大于根，并且根大于另一个子树中的所有树）。
新根比其两个子根都小。然后，使用上述分析的略微修改版本，我们可以证明生成的树确实是堆。
而且，由于子堆的每一步的高度都减少一，因此该算法的总运行时间必须为O（h）。
在这一点上，我们有一个简单的生成堆的算法：
由于在每个步骤中我们都知道到目前为止所拥有的堆是有效的最大堆，因此最终会产生有效的总体最大堆。如果我们很聪明地选择要创建多少个单例堆，那么最终也会创建完整的二叉树。
但是，这似乎应该在O（n lg n）的时间内运行，因为我们进行了O（n）合并，每个合并都在O（h）进行，在最坏的情况下，我们要合并的树的高度是O（lg n）。但是这个界限并不严格，我们可以通过更加精确的分析来做得更好。
特别地，让我们考虑一下我们合并的所有树有多深。大约一半的堆的深度为零，然后剩下的一半的深度为一，然后剩下的一半的深度为二，依此类推。
0 * N / 2 + 1 * N / 4 + 2 * N / 8 + … + NK /（2 ķ）=Σ K = 0 ⌈logn⌉（NK / 2 ķ）= NΣ K = 0 ⌈对数n⌉（k / 2 k + 1）
这是进行交换的上限。每个交换最多需要两个比较。因此，如果我们将上述总和乘以2，我们将得到以下总和，该总和是进行掉期交易的上限：
nΣk = 0∞（k / 2 k）
这里的求和是求和0/2 0 + 1/2 1 + 2/2 2 + 3/2 3 + …。这是一个著名的总结，可以用多种不同的方式进行评估。这些演讲幻灯片，幻灯片45-47中给出了一种评估此问题的方法。最终精确到2n，这意味着最终进行的比较的数量肯定从上方受到3n的限制。
希望这可以帮助！
