Fre*_*hao 9 c++ algorithm heap
我想知道C++中make_heap的算法是什么,复杂度是3*N？只有通过插入元素才能构建堆的方法才有O(N Log N)的复杂性.非常感谢!
bti*_*lly 15
您将堆表示为数组.i第th个元素下面的两个元素位于2*i+1和2*i+2.如果数组有n元素,那么从最后开始,取出每个元素,让它"落"到堆中的正确位置.这是O(n)运行.
为什么？对于n/2元素来说,没有孩子.因为n/4有一个高度为1的子树.因为n/8有一个高度为2 n/16的子树.对于高度为3的子树.依此类推.所以我们得到了这个系列.所以总数"看看我是否需要再摔倒一次,如果是这样,我会摔倒哪种方式？比较来了.但是你可以从离散化中得到完全的结果,所以你总是会出现少于掉头的数据每个最多需要3个比较.(比较每个孩子的根,看它是否需要摔倒,如果根比两个孩子都要大,那么孩子们就会相互比较.)n/22 + 2*n/23 + 3*n/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 = nnn