{algo} 排序算法：堆排序

什么是最大堆
最大堆就是一棵二叉树。满足两点性质：

1. 父结点的键值大于子结点的键值。
2. 左子树和右子树也是堆。

同理可知什么是最小堆。

一般用数组来表示堆。通过下标可以计算出父节点（i/2)，子节点2×i, 2×i+1。

如何建立最大堆
从堆的一半处开始（剩下的一半是叶子）将子堆的堆顶元素下沉。循环操作直到根。

如何堆排序
建立最大堆之后，堆顶元素为最大。将他与最后的元素交换。最后的元素成为第一个元素后，在[1, count-1]范围内将他下沉，推出下一个堆顶。
重复此操作，count不断减1，直到等于2。

详细带图的流程参见这篇文章

代码：

#max heap

def BuildMaxHeap(numbers, heapCount, less):
    # form (heapCount/2) to 1, let heap down
    for startIndex in range((int)(heapCount / 2), 0 , -1):
        MaxHeapDown(numbers, startIndex, heapCount,less)
    pass

def MaxHeapDown(numbers, startIndex, heapCount,less):
    child = startIndex*2 # left child
    temp = numbers[startIndex-1]

    while startIndex <= heapCount / 2:
        # find the max child [if child == heapCount, means right child donot exist]
        if child < heapCount and less(numbers[child-1], numbers[child]):
            child = child + 1

        # if parent not less than child, no need to go down.
        if not(less(temp, numbers[child - 1])):
            break
        
        # if child bigger than parent, lift child up
        numbers[startIndex-1] = numbers[child-1]

        # parent go down
        startIndex = child
        child = startIndex*2

    numbers[startIndex-1] = temp

def ThenHeapSort(numbers, heapCount, less):
    for count in range((int)(heapCount), 1 , -1):
        RemoveHeap(numbers, 1, count-1, less)

def RemoveHeap(numbers, startIndex, heapCount, less):
    # put the biggest number(first) at the last, like removed. put the last number at first.
    numbers[startIndex-1], numbers[heapCount] = numbers[heapCount], numbers[startIndex-1]
    # let the first number go down, select the next bigget number
    MaxHeapDown(numbers, startIndex, heapCount, less)

def leftless(a,b):
    return a<b

def rightless(a,b):
    return a>b

def HeapSort(numbers, heapCount, less=leftless):
    BuildMaxHeap(numbers, len(numbers), less)
    ThenHeapSort(numbers, len(numbers), less)


def TestHeap():
    numbers = [16,32,55,61,78,34,78,11,25,64,91,88,67,120]
    print(numbers)
    
    HeapSort(numbers, len(numbers))
    print(numbers)

    HeapSort(numbers, len(numbers), rightless)
    print(numbers)

if __name__ == '__main__':
    TestHeap()