堆排序的运行时间
算法导论6.4-5
证明：在所有元素不同时，堆排序算法的最佳运行时间是O(nlgn)
算法导论 堆排序 运行时间
[解决办法]
楼主小姑娘，你的命题抄错了，呵呵！
最好情况下，堆排序复杂度为Ω(nlgn)
即证明堆排序复杂度不会小于nlgn！
考虑堆排序的过程，弹出当前最大元素后，将最长路径序列往上拉一层，再将末尾元素放置到最长路径序列的合适位置。
可以看到，由于元素互不相同，除max-heapify的叶子结点外，其余元素均一层一层向根结点靠拢。
假设非叶子结点与根结点距离为h，则当此元素弹出时(已经被排好序)，恰好被移动h次，序号为i的非叶子结点，与根结点距离为[lgi](以下论证忽略取整函数)
如果能证明有一半以上的结点，在max-heapify 中均没有作过叶子结点，则这些结点的移动总次数 S > lg1 + lg2 + ... +lg(n/2) ≈ (n/2) lg(n/2) = (n/2)lgn - n/2 ，
于是得到堆排序时间复杂度为Ω(nlgn)
为简单起见，考虑满二叉树，设最底层叶子结点个数为2^(h+1)，总结点数为2^(h+2) - 1，则排序好2^(h+1) 个元素后，最多有(2^h个)的叶子结点已经排好序。
反证法，假设有>=2^h+1个叶子结点已经排好序，则原有叶子结点的所有父结点均已排好序。根据抽屉原理，这些叶子结点包括了根结点某个子树的所有叶子，
而且还包括另一子树的至少一个叶子结点，根结点某一个子树共有2^(h+1)-1个结点，另一个子树至少有lg(n)个结点已经排好序，而 2^(h+1)-1 + lg(n) > 2^(h+1)，矛盾。
因此对于满二叉树，最底层叶子结点个数全部处理一次后，总共排好了2^(h+1)个元素，其中至少有2^h个元素在max-heapify 中不是叶子结点，这些结点需要一层一层的移动到根结点才能排好序。
即一次处理2^(h+1)个元素后，至少有2^h个元素在max-heapify 中不是叶子结点，使用数学归纳，当全部处理完n个元素后，至少有n/2个元素在max-heapify 中不是叶子结点，于是命题得证
楼主可以查看下我的文章，非常感谢！
很感谢楼主的文章，使我受益非浅，谢谢！
