#coding:utf-8

'''python3 code
author's email: chenyan@feling.net

堆排序
堆的相关性质:
i 的子节点为2i+1, 2i+2(可以自己推出来)
所以i的父节点是(i-1)//2或者(i-2)//2,即:(i-1)/2然后向下取整,即(i-1)//2

我只知道是这么用的而已:
创建堆的时候,从最后一个父节点开始筛选,最后一个节点为i,则最后一个父节点是(i-1)//2
对一个节点筛选,是在三角形中把最值放到顶端,然后继续向下筛选交换了的节点,直到节点没有子节点

'''

def heapsort(l, increase=True):
    '''
    l:待排序列表
    increase:是否从小到大排
    >>> l = [30,8,10,9]
    >>> heapsort(l)
    >>> l
    [8, 9, 10, 30]

    >>> l = [30,8,10,9]
    >>> heapsort(l, False)
    >>> l
    [30, 10, 9, 8]

    >>> l = [-1,-4,0]
    >>> heapsort(l)
    >>> l
    [-4, -1, 0]

    >>> l = [1,2,3,0]
    >>> heapsort(l)
    >>> l
    [0, 1, 2, 3]
    '''
    def small_top(i, len_l):
        '''
        筛选小顶堆
        '''
        top = i
        max_index = len_l - 1
        while top <= (max_index-1)//2:
            c1 = 2 * top + 1
            c2 = 2 * top + 2
            smaller_c = c2 if c2<=max_index and l[c2]<l[c1] else c1
            if l[top]>l[smaller_c]:
                l[top], l[smaller_c] = l[smaller_c], l[top]
            top = smaller_c
    
    def big_top(i, len_l):
        '''
        筛选大顶堆
        '''
        top = i
        max_index = len_l - 1
        while top <= (max_index-1)//2:
            c1 = 2 * top + 1
            c2 = 2 * top + 2
            bigger_c = c2 if c2<=max_index and l[c2]>l[c1] else c1
            if l[top]<l[bigger_c]:
                l[top], l[bigger_c] = l[bigger_c], l[top]
            top = bigger_c

    len_l = len(l)
    max_index = len_l - 1
    sift = big_top if increase else small_top

    for i in range((max_index-1)//2,-1,-1):
        sift(i, len_l)

    for i in range(max_index,0,-1):
        l[0], l[i] = l[i], l[0]
        sift(0, i)   

if __name__=='__main__':
    import doctest
    doctest.testmod()