堆排序

插入

向一个原本有序的数组[1,2,……,n-2]中插入一个元素，只需要找到最后一个元素的位置，保持堆的结构，所以调整index=n的位置即可→上浮

删除

1. 删除叶节点，直接删除
2. 删除非叶节点i，等价于=将其与最后一个元素交换位置，再删除最后一个元素
   此时从节点i开始往下的结构，全部有可能受影响→现在节点i的节点需回到它应该在的位置，下沉

堆排序

堆排序的操作=不断的插入+删除。然而由于实际上一开始我们就拿到了全部的元素，因此一个个插入到堆的操作可以省略。

• 建堆的操作=自下而上每个元素进行下沉。下沉既可以递归地实现（pecdown（i）=i和左右儿子比较+pecdown（i左右儿子中较小的那个））也可以用循环一步到位。

# percDown的递归实现
def percDown(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]  # 交换
  
        percDown(arr, n, largest) 

# percDown的循环实现
def percDown(arr, n, i):
    while 2 * i + 1<n:
        # largest指向左右儿子较大的那个 
        l = 2 * i + 1     # left = 2*i + 1 
        r = 2 * i + 2     # right = 2*i + 2 
        largest = i

        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]  # 交换
            i = largest 
        else:
            break

def heapSort(arr): 
    n = len(arr) 
  
    # Build a maxheap. 
    for i in range(n//2, -1, -1): # percDown会检验下标，从n开始也可
        percDown(arr, n, i) 
  
    # 一个个交换元素
    for i in range(n-1, 0, -1): 
        arr[i], arr[0] = arr[0], arr[i]   # 交换
        percDown(arr, i, 0) 

arr = [ 12, 11, 13, 5, 6, 7] 
heapSort(arr) 
n = len(arr) 
print ("排序后") 
for i in range(n): 
    print ("%d" %arr[i])