本文共 456 字，大约阅读时间需要 1 分钟。

建堆的过程，看起来外面一层循环O(n)，里面是个logn的调整函数，时间复杂度貌似是nlogn的，但是仔细分析，其实质是O(n)的。

证明如下：

首先，对于高度为h的完全二叉树，其第i层的元素个数为2^(i-1)，对于堆的每一层，调整的深度都不一样，每层的元素的调整深度小于等于h-i，假设每层调整的深度是h-i，欲构建的堆是个完全二叉树，那么对于每层来说：

最后一层不用调整；

倒数第二层的消耗是：2^(h-1)*1；

倒数第三层的消耗是：2^(h-2)*2；

。。。。。。

第一层的消耗是：2^(h-h)*(h-1)；

加起来总消耗是：S=2^(h-1)*1+2^(h-2)*2+。。。+h；

2S=2^h*1+2^(h-1)*2+。。。+2*h；

S=2^h+2^(h-1)+2^(h-2)+。。。+2^1-h；

S=2^h+2^(h-1)+2^(h-2)+。。。+2^1+2^0-h-1；

S=2^(h+1)-2-h；

h=logn；

代入得：S=2*n-2-logn；

故堆排序的建堆过程是O(n)的。

转载地址：http://ylgsi.baihongyu.com/