分析

堆排序的核心函数是heapify。在buildHeap中，这个函数将会被调用n/2」-1次，在实际排序中，它也会被调用n-1次，总共调用了3n/2」-2次。如你所见，这是一个递归的操作，在到达堆的底部之前会执行固定数目的计算。因为形状的性质，堆的深度将会是(3n/2」-2)*log(n)」，n是堆中元素的数目。性能是O(n log n)。