问题描述
我不知道什么是make_heap的算法在C ++中，这样的复杂度是3 * N？只有这样我能想到的通过插入元素具有复杂性为O（N日志N）作堆。非常感谢！
I wonder what's the algorithm of make_heap in in C++ such that the complexity is 3*N? Only way I can think of to make a heap by inserting elements have complexity of O(N Log N). Thanks a lot!
推荐答案
您重新present堆作为数组。下面的我这两个元素的个元素是在位置 2 * I + 1 和 2 * 1 + 2 。如果数组有 N 元素的话，从月底开始，每次取元素，让它落到堆中正确的地方。这是 O（N）运行。
You represent the heap as an array. The two elements below the i'th element are at positions 2*i+1 and 2*i+2. If the array has n elements then, starting from the end, take each element, and let it "fall" to the right place in the heap. This is O(n) to run.
为什么呢？元素悉心为 N / 2 有没有孩子。对于 N / 4 有身高1的子树 N / 8 有身高2的子树。对于 N / 16 高度3等等的子树。所以，我们得到了一系列 N / 2 + 2 * N / 2 + 3 * N / 2 + ... =（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 ，但你得到四舍五入的离散化，所以你总是出来小于 N 套掉期找出每一个都需要至多3的比较。（比较根每个孩子是否需要下跌的话，孩子们互相如果根比两个孩子大的。）
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/2 + 2*n/2 + 3*n/2 + ... = (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. So the total number of "see if I need to fall one more, and if so which way do I fall? comparisons comes to n. But you get round-off from discretization, so you always come out to less than n sets of swaps to figure out. Each of which requires at most 3 comparisons. (Compare root to each child to see if it needs to fall, then the children to each other if the root was larger than both children.)
这篇关于如何make_heap用C ++实现有3N的复杂性？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！