本文主要是介绍堆排序中建堆过程的时间复杂度O(n)的证明，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
下面是建立大根堆的代码
- template <typename Type>
- void CreateBigRootHeap(Type *array, int len)
- {
- int i, j, k;
- Type temp;
- for (i = (len - 1) / 2; i >= 0; --i)
- {
- temp = array[i];
- k = i;
- for (j = i * 2 + 1; j < len; j = j * 2 + 1)
- {
- if (j < len - 1 && array[j] < array[j + 1])
- j += 1;
- if (temp > array[j])
- break;
- array[k] = array[j];
- k = j;
- }
- array[k] = temp;
- }
- }
令堆所对应的完全二叉树的高度为h，节点的个数为n，现假定完全二叉树为满二叉树：即n = 2^h - 1,如下图（借用网上的图）所示
有2^(h-2)个结点向下访问一次，2^(h-3)个结点向下访问2次，...1个结点向下访问h-1次(之前写错了，写成了h次，下面公式最后也应该是h-1， 因为好久了不好改了，抱歉)：
推导公式如下：
在堆所对应的二叉树为非满二叉树时，复杂度是n同阶的。
转载http://blog.csdn.net/anonymalias/article/details/8807895
这篇关于堆排序中建堆过程的时间复杂度O(n)的证明的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
