我想知道C++中make_heap的算法是什么,复杂度为3*N?我能想到的通过插入元素来创建堆的唯一方法的复杂度为 O(N Log N)。多谢!
您将堆表示为数组。下面的两个元素i
'第一个元素位于位置2i+1
and 2i+2
。如果数组有n
然后,从末尾开始取出每个元素,并让它“落入”堆中的正确位置。这是O(n)
to run.
Why? Well for n/2
of the elements there are no children. For n/4
there is a subtree of height 1. For n/8
there is a subtree of height 2. For n/16
a subtree of height 3. And so on. So we get the series n/22 + 2n/23 + 3n/24 + ... = (n/2)(1 * (1/2 + 1/4 + 1/8 + . ...) + (1/2) * (1/2 + 1/4 + 1/8 + . ...) + (1/4) * (1/2 + 1/4 + 1/8 + . ...) + ...) = (n/2) * (1 * 1 + (1/2) * 1 + (1/4) * 1 + ...) = (n/2) * 2 = n
. Or, formatted maybe more readably to see the geometric series that are being summed:
n/2^2 + 2n/2^3 + 3n/2^4 + ...
= (n/2^2 + n/2^3 + n/2^4 + ...)
+ (n/2^3 + n/2^4 + ...)
+ (n/2^4 + ...)
+ ...
= n/2^2 (1 + 1/2 + 1/2^4 + ...)
+ n/2^3 (1 + 1/2 + 1/2^3 + ...)
+ n/2^4 (1 + 1/2 + 1/2^3 + ...)
+ ...
= n/2^2 * 2
+ n/2^3 * 2
+ n/2^4 * 2
+ ...
= n/2 + n/2^2 + n/2^3 + ...
= n(1/2 + 1/4 + 1/8 + ...)
= n
我们反复使用的技巧是我们可以将几何级数与
1 + 1/2 + 1/4 + 1/8 + ...
= (1 + 1/2 + 1/4 + 1/8 + ...) (1 - 1/2)/(1 - 1/2)
= (1 * (1 - 1/2)
+ 1/2 * (1 - 1/2)
+ 1/4 * (1 - 1/2)
+ 1/8 * (1 - 1/2)
+ ...) / (1 - 1/2)
= (1 - 1/2
+ 1/2 - 1/4
+ 1/4 - 1/8
+ 1/8 - 1/16
+ ...) / (1 - 1/2)
= 1 / (1 - 1/2)
= 1 / (1/2)
= 2
因此,“看看我是否需要再摔一次,如果需要的话,我应该从哪条路上摔下来?”比较的总数为n
。但是你会从离散化中四舍五入,所以你总是会小于n
需要计算出的交换集。每个最多需要 3 次比较。 (将根与每个子项进行比较,看看它是否需要掉落,如果根比两个子项都大,则将子项相互比较。)
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)