Python 堆排序

作为一个菜鸟，感觉源代码的注释写得太少了，以下做点注解吧。

关键有3个点：

1、先把堆调成小根堆的状态，方法是在每个结点的所有根部中确定它的位置；

2、heapify函数实际上是对传入的arr[i]点在其所有根部中确定它的位置；

3、堆头与堆尾交换，此后堆尾退出堆，堆的范围缩小1，公式中i即为堆的长度，之后再将新到堆首的点放在合适的位置，因为其他点均已在正确的位置上，其他点最多与新点交换一次。

def heapify(arr, n, i): 

   largest = i  

   l =2* i +1     # left = 2*i + 1

   r =2* i +2     # right = 2*i + 2

   if l < n and arr[i]< arr[l]: 

       largest = l

   if r < n and arr[largest]< arr[r]: 

       largest = r

   if largest != i: 

       arr[i],arr[largest]= arr[largest],arr[i]  # 交换

       # 此时largest位置的数字（也就是最开始输入那个lis[i]）处于待定状态，需要在它所有根部中确定其位置

       heapify(arr, n, largest) 

def heapSort(arr): 

   n = len(arr) 

   # Build a maxheap.

   for i in range(n,-1,-1): 

       # 先把堆调整好小根堆的状态，在全堆中逐个调整每个数字的位置，调整的方法是在它所有根部中确定其位置

       heapify(arr, n, i) 

   # 一个个交换元素

   for i in range(n-1,0,-1): 

       arr[i], arr[0]= arr[0], arr[i]   # 交换

       # 把新上来的0号安排到合适的位置上去,其中i指的是要调整的堆的范围

       heapify(arr, i,0)