本文主要是介绍堆的时间复杂度分析，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一，建堆的时间复杂度分析
堆是一颗完全二叉树，满二叉树又是一颗特殊的完全二叉树。
对于满二叉树来说，第一层的节点个数为2^0,第二层的节点个数为2^1,......所以可以得到第h层的节点个数为2^(h-1)。总结点个数N=2^0+2^1+...+2^(h-1)=2^h-1。那么就可以得出高度和节点个数的关系h=log（N+1）。
对于完全二叉树来说，最少情况下是上图中，最后一层只有一个节点，最多情况就是一个满二叉树。最少情况下，N=2^0+2^1+...+2^(h-2)+1=2^(h-1),同样高度和节点个数的关系：h=logN+1;
向上调整建堆和向下调整建堆的算法（内容在上一节中），最坏情况下都是要调整高度次，所以时间复杂度都是O(logN).
二，堆排序的时间复杂度分析
堆排序的大致思路：先将数据建堆（有4，），再将堆顶数据和最后一个数据交换，将除最后一个数据外的剩下数据重新建堆，反复执行，最大或最下的数据就会被放在后面，最后就得到一组有序数据。
//堆排序
void HeapSort(int* a, int n)
{//升序，建大堆//降序，建小堆//向下调整建堆//从第一个非叶子节点开始for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}int end = n - 1;while (end > 0){swap(&a[0], &a[end]);//交换AdjustDown(a, end, 0);//重新建堆end--;}
}1，使用向下调整建堆
可能在只看代码时，会认为一个for循环，加上向下调整算法，时间复杂度是O(N*logN),其实不然，时间复杂度是O(N)。
向下调整建堆的思路：从第一个非叶子节点开始，使用向下调整算法，使它的左右子树都调成大堆或者小堆，依次循环。
时间复杂度分析：
第一层有2^0个节点，每个节点最多向下调整h-1次。
第二层有2^1个节点，每个节点最多向下调整h-2次。
第三层有2^2个节点，每个节点最多向下调整h-3次。
......
第h-1层有2^(h-2)个节点，每个节点最多向下调整1次。
最多需要调整的次数：
F(h)=2^0*(h-1)+2^1*(h-2)+2^2*(h-3)+...+2^(h-2)*1
2F(h)=2^1*(h-1)+2^2*(h-2)+2^3*(h-3)+...+2^(h-1)*1
相减得：F(h)=2^(h-1)+2^1+2^2+...+2^(h-2)-2^0*(h-1)
最后得：F(h)=2^h-1-h，再将h=logN代入：
F(h)=N-1-logN.（N的量级大于logN的量级）
所以向下建堆的时间复杂度为O(N)
2,使用向上调整建堆
向上调整建堆与向下相比，时间复杂度会更高。
//堆排序
void HeapSort(int* a, int n)
{//升序，建大堆//降序，建小堆//向上调整建堆for (int i = 1; i < n; i++){AdjustUp(a, i);}int end = n - 1;while (end > 0){swap(&a[0], &a[end]);AdjustDown(a, end, 0);end--;}
}
向上调整建堆的思路：将第一个数据看成是堆，从第二个数据开始，调用向上建堆算法，入一个数据，调用一次建堆。
时间复杂度分析：（从第二行开始）
第二行2^1个数据，每个数据向上调整1次
第三行2^2个数据，每个数据向上调整2次
......
第h行2^(h-1)个数据，每个数据向上调整h-1次
最多需要调整的次数：T(h)=2^1*1+2^2*2+...+2^(h-1)*(h-1)
2T(h)=2^2*1+2^3*2+...+2^h*(h-1)
相减得：T(h)=2^h*(h-1)-2^1-（2^2+2^3+...+2^(h-1))
T(h)=2^h*(h-1)-2^h+2
得：T(h)=(N+1)*(log(N+1)-1)-N+1
这个公式看最后一项就可以看出时间复杂度是O(N*logN),因为最后一行有2^(h-1)个节点，占整颗树节点的一半,还要调整h-1次。
3，比较
其实不难看出，向下建堆过程中，规律是：节点数量多的层*调整次数少，节点数量少得层*调整次数多。
向上建堆过程就相反，节点数量多的层*调整次数多，节点数量少得层*调整次数少。
所以向下调整建堆得时间复杂度更低。堆排序中用的也就是向下调整建堆。
4，重新建堆过程时间复杂度
while (end > 0)
{swap(&a[0], &a[end]);AdjustDown(a, end, 0);end--;
}该过程是将建好的堆进行调整，交换堆顶数据和最后一个数据，然后将最后一个数据除外，重新形成一个堆，反复执行，使数据变得有序。
时间复杂度分析：
该过程每次都要调整，都是从第一个节点位置开始，N个节点，最多调整logN次，在加上一次循环，最多调整N*logN次。
该过程的时间复杂度是O(N*logN)
堆排序的时间复杂度为：O(N*logN)+O(N), 其中N*logN的量级更大
总结：堆排序的时间复杂度为O(N*logN)
这篇关于堆的时间复杂度分析的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
