我们首先要明晰几点：1，算堆排序的时间复杂度算的是交换次数而不是比较次数。2，设数据个数为N，高度便为lg N。3，为了推算最坏情况，我们用满二叉树，并且N无限大， lg N也无限大 
建堆的时间复杂度
为了追求效率，一般选用向下调整建堆。从倒数第二层的最后一个节点开始向下调整，这一层一共有1/4N个节点，最坏情况下每个节点都要向下调整一次，这一层最坏调整1/4N次，倒数第三层有1/8N个节点，最坏情况下每个节点都要向下调整两次，所以倒数第三层最坏要调整1/4N次，倒数第四层有1/16N个节点，最坏情况下每个节点都要向下调整3次，所以倒数第四层最坏情况最坏要调整3/16N次，这三层已经接近3/4N次了，一次往后推，整个向下调整建堆的交换次数接近N次，所以建堆的时间复杂度在O(N)这个量级。
排序的时间复杂度
排序时会让第一个数据和最后一个数据交换，让最后一个数据在第一个数据的位置向下调，直到符合堆的排列规则为止，然后总数减一。最后一层有1/2N个数据,最坏情况下，每个数据都要和第一个数据较换并且向下调整，而下调最坏情况是高度次减一，也就是lg N - 1，因为lg N特别大， lg N ==
lg N - 1。所以最后一层最坏情况是交换1/2N * lg N次，倒数第二层也同理，lg N - 2 == lg N,倒数第三层也同理。所以整体的交换次数是趋近于 N * lg N的，所以排序的时间复杂度在N * lg N这个量级。
堆排序的时间复杂度
把上述的时间复杂度相加的 N + N * lg N == N(1 + lg N),由于lg N 特别大，1可以忽略不计， 所以堆排序的时间复杂度在 N * lg N这个量级。
