堆排序有点像先二分法找极大值，再冒泡排序：

# 假定数组最后一位是根节点，其他部分平分为分支节点
# 经过一次OneHeapSort，找到最大值并放到根节点
def OneHeapSort(list, l, r):
    if r-l<=0:
        return
    if r-l==1 and list[l]>list[r]:
        list[l],list[r] = list[r],list[l]
    else:
        middle = l + (r-l-1)//2
        OneHeapSort(list, l, middle)
        OneHeapSort(list, middle+1, r-1)
        if list[middle]>list[r]:
            list[middle],list[r] = list[r],list[middle]
        if list[r-1]>list[r]:
            list[r-1],list[r] = list[r],list[r-1]

# 依次将最大值放到数组的后面
def heapSort(list):
    for i in range(len(list)-1, 0, -1):
        OneHeapSort(list, 0, i)


list = [1, 10, 8, 200, 50, 4]
heapSort(list)
print(list) # [1,4,8,10,50,200]

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

关键有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)