def heapify(A):
for root in xrange(len(A)//2-1, -1, -1):
rootVal = A[root]
child = 2*root+1
while child < len(A):
if child+1 < len(A) and A[child] > A[child+1]:
child += 1
if rootVal <= A[child]:
break
A[child], A[(child-1)//2] = A[(child-1)//2], A[child]
child = child *2 + 1
这是python heapq的类似实现.heapify().文档中说这个函数在O(n)中运行.但对于n/2个元素，它会记录(n)个操作.为什么是O(n)？
这需要更仔细的分析，比如你会发现.基本观点是，只有堆的根实际上具有深度log2(len(a)).在叶子上方的一个 node 上——有一半的 node 位于该 node 上——在第一次内部循环迭代中，一片叶子被击中.
挥舞双手，当算法在一个包含N个元素的子树的根 node 上查看 node 时，每个子树中大约有N/2个元素，然后需要与log(N)成比例的功才能将根和这些子堆合并到一个堆中.所以总共需要T(N)个小时
T(N) = 2*T(N/2) + O(log(N))
这是一种罕见的复发.不过，Akra–Bazzi method可以用来推断它是O(N).
我认为，从零开始推导出一个精确的解决方案更能提供信息，当然也更令人满意.为此，我将只讨论完整的二叉树:在每个级别上尽可能完整.然后总共有2**N - 1个元素，所有子树也是完整的二叉树.这回避了一大堆毫无意义的细节，比如当事情不完全平衡时如何处理.
当我们看一个包含2**k - 1个元素的子树时，它的两个子树每个元素正好有2**(k-1) - 1个元素，有k个级别.例如，对于包含7个元素的树，根上有1个元素，第二层有2个元素，第三层有4个元素.子树重设后，根必须移动到位，将其向下移动0、1或2级.这需要在0级和1级之间进行比较，也可能在1级和2级之间进行比较(如果根需要向下移动)，但仅此而已:所需的功与k-1成正比.总之，
T(2**k - 1) = 2 * T(2**(k-1) - 1) + (k - 1)*C
对于某些常数C，边界是比较两个相邻级别上的元素的最坏情况.
T(1)美元怎么样？那是免费的！一棵只有一个元素的树已经是一个堆了——没什么可做的.
T(1) = 0
在这些叶子之上一层，树木有三种元素.将最小的(对于最小堆；对于最大堆)移动到顶部需要(不超过)C美元.
T(3) = C
一级以上的树有7个元素.对每个子树进行重分类需要花费T(3)美元，然后将根移动到位不超过2*C美元:
T(7) = 2*C + 2*C = 4*C
继续以同样的方式:
T(15) = 2* 4*C + 3*C = 11*C
T(31) = 2*11*C + 4*C = 26*C
T(63) = 2*26*C + 5*C = 57*C
...
T(2**k - 1) = (2**k - k - 1)*C
最后一行是对一般形式的猜测.你可以验证"它适用于"之前的所有特定行，然后用归纳法证明它很简单.
那么，N = 2**k - 1，
T(N) = (N - log2(N+1)) * C
这表明T(N)以C*N为界，当然O(N)也是.