Cap*_*ffe 28 c++ algorithm big-o stl binary-heap
我查看了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将不胜感激.
编辑:
实验结果:
这个实际实现使用
tem*_*def 53
使用巧妙的算法和巧妙的分析,可以在O(n)时间内创建n个元素上的二进制堆.接下来我将谈谈假设你有明确的节点和明确的左右子指针这是如何工作的,但是一旦你将它压缩成一个数组,这个分析仍然是完全有效的.
该算法的工作原理如下.从大约一半的节点开始,将它们视为单例最大堆 - 因为只有一个元素,只包含该元素的树必须自动成为最大堆.现在,把这些树和彼此配对.对于每对树,请使用尚未使用的值之一并执行以下算法:
使新节点成为堆的根,使其左右子指针引用两个max-sheaps.
虽然此节点的子节点大于它,但将子节点与其较大的子节点交换.
我的主张是这个过程最终产生一个包含两个输入最大堆的元素的新的最大堆,并且它在时间O(h)中这样做,其中h是两个堆的高度.证明是对堆高度的归纳.作为基本情况,如果子堆的大小为零,则算法立即终止于单个最大堆,并且它在O(1)时间内终止.对于归纳步骤,假设对于某些h,此过程适用于任何大小为h的子堆,并考虑当您在两个大小为h + 1的堆上执行时会发生什么.当我们添加一个新的根以将两个大小的子树连接在一起时h + 1,有三种可能性:
新根大于两个子树的根.然后在这种情况下,我们有一个新的最大堆,因为根大于任何子树中的任何节点(通过传递性)
新根大于一个孩子,小于另一个孩子.然后我们将根与较大的子子项交换,并使用旧的根和子的两个子树(每个子树的高度为h)再次递归地执行此过程.通过归纳假设,这意味着我们交换的子树现在是最大堆.因此整个堆是一个最大堆,因为新的根大于我们交换的子树中的所有东西(因为它比我们添加的节点大,并且已经比那个子树中的所有东西都要大),并且它也比一切都大在另一个子树中(因为它大于根,并且根大于其他子树中的所有子树).
新根比其子女小.然后使用上面分析的略微修改版本,我们可以证明生成的树确实是一个堆.
此外,由于在每个步骤中子堆的高度减少1,因此该算法的总运行时间必须为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 ⌈ logn⌉(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以上.
希望这可以帮助!
ham*_*mar 17
@templatetypedef已经为渐近运行时间为O(n)的原因提供了一个很好的答案.CLRS第2版第6章也有证据.build_heap
至于为什么C++标准要求使用最多3n个比较:
从我的实验(见下面的代码)来看,实际上需要不到2n个比较.事实上,这些讲义包含一个build_heap仅使用2(n-⌈logn⌉)比较的证明.
标准的界限似乎比要求更慷慨.
def parent(i):
return i/2
def left(i):
return 2*i
def right(i):
return 2*i+1
def heapify_cost(n, i):
most = 0
if left(i) <= n:
most = 1 + heapify_cost(n, left(i))
if right(i) <= n:
most = 1 + max(most, heapify_cost(n, right(i)))
return most
def build_heap_cost(n):
return sum(heapify_cost(n, i) for i in xrange(n/2, 1, -1))
一些结果:
n 10 20 50 100 1000 10000
build_heap_cost(n) 9 26 83 180 1967 19960