建堆O(n)时间复杂度证明

建堆复杂度先考虑满二叉树，计算完全二叉树建堆复杂度基本相同。

对满二叉树而言，第i层(根为第0层)有2^i个节点。由于建堆过程自底向上，以交换作为主要操作，因此第i层任意节点在最不利情况下，需要经过(n-i)次交换操作才能完成以该节点为堆根节点的建堆过程。因此，时间复杂度计算如下：

T(n) = 2^0 * (n - 0) + 2^1 * (n - 1) + ... + 2^n * (n - n) = sum((n - i) * 2^i)

采用错位相减法：

• 原式乘2得：
• T(n) * 2 = 2^1 * (n - 0) + 2^2 * (n - 1) + ... + 2^(n+1) * (n - n)
• = sum((n - i) * 2^(i+1))
• 原式如下：
• T(n) = 2^0 * (n - 0) + 2^1 * (n - 1) + ... + 2^n * (n - n)
• = sum((n - i) * 2^i)
• 相减得：
• 2T(n) - T(n) = -n + 2^1 + 2^2 + ... + 2^n = 2 * (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 - logN / N - 2 / N) ≈ N

故时间复杂度为O(N)，得证。