建堆的复杂度先考虑满二叉树，和计算完全二叉树的建堆复杂度一样。
对满二叉树而言，第 \(i\) 层(根为第 \(0\) 层)有 \(2^i\) 个节点。
由于建堆过程自底向上，以交换作为主要操作，因此第 \(i\) 层任意节点在最不利情况下，
需要经过 \((n - i)\) 次交换操作才能完成以该节点为堆根节点的建堆过程。
因此，时间复杂度计算如下：
\(T(n) = 2^0 * (n - 0) + 2^1 * (n - 1) + ... + 2^n * (n - n) = \sum_{i = 0}^{n}(2^i * (n - i))\)
将上式乘以 \(2\)得：
\(2*T(n) = 2^1 * (n - 0) + 2^2 * (n - 1) + ... + 2^{n+1} * (n - n) = \sum_{i = 1}^{n+1}(2^i * (n - i))\)
原式减去上式得：
\(2T(n) - T(n) = -n + 2^1 + 2^2 + ... + 2^n = 2 * \frac{1 - 2^n} {1 - 2} - n = 2^{n+1} - 2 - n\).
上面推导中，\(n\) 为层数编号（自 \(0\) 层根节点开始）。
故总节点数为 \((1 + 2 + 4 + ... + 2^n) = 2^{n+1} - 1\)。
渐进时，忽略减 \(1\) 取 \(N ＝ 2^{n+1}\) 。
所以，\(T(N) = 2^{n+1} - n - 2 = N * (1 - \frac{logN} { N} - \frac{2} {N}) ≈ N\).
所以，建堆的时间复杂度为 \(O(N)\) ，得证。\(N\)为总节点数。
转载于:https://www.cnblogs.com/LzyRapx/p/9565305.html
