如何实现C ++中的make_heap具有3N的复杂性？ [英] How is make_heap in C++ implemented to have complexity of 3N?

问题描述

我想知道在C ++中make_heap的算法是什么，复杂性是3 * N？只有我能想到的通过插入元素有一个复杂的O（N Log 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!

推荐答案

将堆表示为数组。 i '下面的两个元素位于 2 * i + 1 和 2 * i + 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 + 2 * n / 2 3 + 3 * n / 2 + ... =（n / 2）（1 *（1/2 + 1/4 + 1/8 + ...）+（1/2）*（1/2 + + ...）+（1/4）*（1/2 + 1/4 + 1/8 + ...）+ ...）=（n / 2）*（1 * 1 + / 2）* 1 +（1/4）* 1 + ...）=（n / 2）* 2 = n 。所以总数看我是否需要跌落一个，如果是这样我怎么下降？比较来到 n 。但是你从离散化的四舍五入，所以你总是出来少于 n 的交换集合，每个最多需要3个比较（比较root到每个孩子，看看是否需要如果根比两个孩子都大，那么孩子们彼此相交。）

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 + 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 = 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.)

这篇关于如何实现C ++中的make_heap具有3N的复杂性？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！