有人能解释一下构建堆的复杂性吗？
将项插入到堆中是O（logn），并且插入被重复n/2次（剩余的是叶子，不能违反堆属性）。所以，我认为这意味着复杂性应该是O（n log n）。
换言之，对于我们“heapify”的每个项目，它有可能必须为堆的每个级别（即logn级别）过滤（即筛选）一次。
我错过了什么？
当前回答
连续插入可通过以下方式描述：
T = O(log(1) + log(2) + .. + log(n)) = O(log(n!))
通过starling近似，n！=~O（n^（n+O（1））），因此T=~O（nlog（n））
希望这有帮助，O（n）的最佳方式是对给定集合使用构建堆算法（排序无关紧要）。
其他回答
基本上，在构建堆时，只在非叶节点上完成工作。。。所做的工作是减少交换量以满足堆条件。。。换句话说（在最坏的情况下），数量与节点的高度成比例。。。总之，问题的复杂性与所有非叶节点的高度之和成正比。。即（2^h+1-1）-h-1=n--1=O（n）
连续插入可通过以下方式描述：
T = O(log(1) + log(2) + .. + log(n)) = O(log(n!))
通过starling近似，n！=~O（n^（n+O（1））），因此T=~O（nlog（n））
希望这有帮助，O（n）的最佳方式是对给定集合使用构建堆算法（排序无关紧要）。
“构建堆的线性时间界限可以通过计算堆中所有节点的高度之和来显示，这是虚线的最大数量。对于包含N=2^（h+1）–1个节点的高度为h的完美二叉树，节点高度之和为N–h–1。因此它是O（N）。"
我们通过计算每个节点可以进行的最大移动量来获得堆构建的运行时。所以我们需要知道每行中有多少个节点，每个节点离它们的距离有多远。
从根节点开始，下一行的节点数是前一行的两倍，因此，通过回答节点数可以增加一倍，直到没有剩余节点，我们可以得到树的高度。或者用数学术语来说，树的高度是log2（n），n是数组的长度。
为了计算一行中的节点，我们从后面开始，我们知道n/2个节点位于底部，所以除以2，我们得到前一行，依此类推。
基于此，我们得到了筛选方法的公式：（0*n/2）+（1*n/4）+（2*n/8）+…+（log2（n）*1）
最后一个段落中的术语是树的高度乘以根处的一个节点，第一个段落中术语是底部行中的所有节点乘以它们可以移动的长度，0。smart中的相同公式：
把n带回来，我们得到了2*n，2可以被丢弃，因为它是一个常数，而tada是Siftdown方法最坏的运行时：n。
如果通过重复插入元素来构建堆，那么它将是O（n log n）。然而，通过以任意顺序插入元素，然后应用算法将它们“堆”成正确的顺序（当然取决于堆的类型），可以更有效地创建新的堆。
看见http://en.wikipedia.org/wiki/Binary_heap，例如“构建堆”。在这种情况下，您基本上从树的底层开始工作，交换父节点和子节点，直到满足堆条件。
