优先队列（堆）的构建时间复杂度分析
本文以最小堆为例，构建堆的过程是首先初始化一个数组a，其中a[0]存数组的长度n，即第一个有效元素从a[1]开始，这样保证左孩子为2*i，右孩子为2*I+1；然后从(n - 1)/2开始，每次向下调整一个元素，直到n = 0。
代码为：
//最小堆
void HeapAdjust(int *a,int i)
{
int n = a[0];
int child;
int p = a[i];
for(;2 * i <= n; i = child)
{
child = 2 * i;
if( child + 1 <= n && a[child] > a[child + 1])
child++;
if(p > a[child])
a[i] = a[child];
else
break;
}
a[i] = p;
}
void HeapSort(int *a)
{
int n = a[0];
for(int i = (n - 1)>>1;i > 0;i--)
HeapAdjust(a,i);
} 下面分析时间复杂度
n个结点的完全二叉树（堆是完全二叉树）的深度为h（根的深度为1），则h和n之间满足 2^(h-2) <n <= 2^h，h近似等于log(n)+1。
从代码的直观来看，每次调整一个结点需要log(n)，一共调整(n-1)/2个结点，故时间复杂度为O(nlogn)，但要注意在中间过程中第s层的结点往下调整时实际只需最多调整（h-s）次，第s层一共调整2^(s-1)*(h-s)，这样时间复杂度可写成：
所以优先队列的构建时间为线性的。
下一篇：
单链表的逆置（递归和非递归）