关于堆排序的最佳时间的问题
各位好：
在《算法导论》第二版 p80 *6.4-5题，说最佳时间为Ω(nlgn).但我觉得堆排序的时间取决于MAX_HEAPIFY的时间，因为BUILD_MAX_HEAP的时间最坏为Ο(n)，当数组A为逆序时(以排序的，例如：n,n-1,n-2,... 当然逆向已排序只是最佳的一种，只要整个数组在最大堆化以前就已是最大堆)时，MAX_HEAPIFY总为常数时间Ο(1)，那么BUILD_MAX_HEAP仍为Ο(n)，但此时HEAPSORT的时间为BUILD_MAX_HEAP + Ο(n) * MAX_HEAPIFY = Ο(n) + Ο(n) * Ο(1) = Ο(n),就不是Ω(nlgn)了。大家认为呢？希望讨论能得到正确结果 有劳各位了 分不多，权当巩固 记忆基本算法吧 10分送上！！
[解决办法]
楼主,这个是大‘O’定义的问题了。堆排序这里总结为O（lgn）是因为找不出比 lg 函数更贴近的一个上界了。
[解决办法]
O(lgn)只是一个上界而已，不是精确界
