【探索数据结构与算法】向上调整建堆与向下调整建堆的时间复杂度

本文主要是介绍【探索数据结构与算法】向上调整建堆与向下调整建堆的时间复杂度，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一.前言

堆排序是一种优于冒泡排序的算法, 那么在进行堆排序之前, 我们需要先创建堆,  那么这个建堆的时间复杂度是多少呢?

二.下调整算法建堆

 因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个结点不影响最终结果)：

假设高度为h的二叉树, 结点的个数为N, 可以计算出高度h与结点个数之间的关系如下图所示:

 

向下调整算法, 从最后一个非叶子结点开始向下调整, 也就是第h-1层, 需要向下移动一层, 第h-2层需要向下移动2层, … , 第一层则需要向下移动h-1层, 第二层的结点需要向下移动h-2层. 依次类推, 如图所示. 

 

移动的次数T(n) 

 

因此下调整建堆的时间复杂度为O(N) 

可以看出节点数量多的层调整次数少, 结点数量少的层调整次数多 . 错位相减法则可以计算出T(N) = 2^h - 1 - h, 带入h与N的关系则得出向下调整建堆的时间复杂度为O(N). 

代码实现 

void HeapSort(int* a, int n)//这里放在堆排序中建堆
{//降序//创建小堆//向下调整创建,从最有一个非叶子节点//时间复杂度O(N)for (int i = (n-1-1)/2; i>=0; i--){Adjustdown(a, n, i);}//堆创建之后,交换第一个节点与最后一个节点,//时间复杂度为O(N*logN)int end = n-1;while (end > 0){Swap(&a[0], &a[end]);Adjustdown(a, end, 0);end--;}
}

 

总计调整次数为 

 

使用错位相减法计算: 

 

可以看出结点数多的层, 调整次数也多, 结点数少的层, 调整次数少, 时间复杂度为O(N*logN), 所以一般建堆都采用向下调整建堆法. 

代码实现 

//放在堆排序中建堆
void Heapsort(int* a,int n)
{//时间复杂度为O(N*logN)for (int i = 1; i < n; i++)//使用for循环建堆{AdjustUP(a, i);}//时间复杂度为O(N*logN)int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);end--;}
}

这篇关于【探索数据结构与算法】向上调整建堆与向下调整建堆的时间复杂度的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---