堆排序

堆排序的思路是先要建立堆
大根堆：所有父节点比子节点要大
小跟堆：所有父节点比子节点小

升序排序先建立大根堆，建立好后，把堆顶部元素和最后一个交换，然后调整堆大小
代码的易错点在建立堆的时候。建立堆的时候，只需要从所有非叶子（len(arr)/2-1）节点开始调整。调整过程可以调用adjust_heap函数，因为所有叶子节点可以看成已经自然成堆的。

def heapSort(arr):

    # build big heap
    i = len(arr) -1
    for i in range(len(arr)/2-1,-1,-1):
        adjust_heap(arr,i,len(arr)-1)

    # 开始堆排序
    for i in range(0,len(arr)-1):
        arr[0],arr[len(arr)-i-1] = arr[len(arr)-i-1],arr[0]
        # adjust heap
        adjust_heap(arr,0, len(arr)-i-2)

# 调整堆 logn复杂度
def adjust_heap(arr, begin, end):
    if end == begin:
        return arr[end]
    start = begin
    while(start<end):
        left = start*2+1
        if left>end:
            break
        right = left + 1
        max_index = left
        if right<=end:
            if arr[left]<arr[right]:
                max_index = right
        if arr[start]<arr[max_index]:
            arr[start],arr[max_index] = arr[max_index],arr[start]
            start = max_index
        else:
            break