跟我一起学 - 算法导论 - 堆

# encoding:UTF-8
#  [递归] - 单条路 自下往上排序 
def  heap_adjust(data, s, m):
     if   2   *  s  >  m: return
   
     #  声明 预设父节点位置
    temp  =  s  -   1
    
     #  [左]子节点值 大于 父节点值  :  预设父节点位置 为 左子节点位置
     if  data[ 2 * s  -   1 ]  >  data[temp]: temp  =   2 * s - 1
    
     #  [右]子节点值 大于 预设父节点 : 预设父节点位置 为 右子节点位置
     if   2   *  s  <=  m  -   1   and  data[ 2 * s]  >  data[temp]: temp  =   2   *  s
    
     #  交换值 满足 堆特性 此为 [ 父节点 小于 子节点  ]
     if  temp  <>  s  -   1 :
        data[s  -   1 ], data[temp]  =  data[temp], data[s  -   1 ]
        heap_adjust(data, temp  +   1 , m)


def  heap_sort(data):
    m  =  len(data)  /   2
     #  构建 堆树
     #  测试数据 [3,2,1] 数组值为 所以非底层叶节点
     for  i  in  range(m , 0,  - 1 ):
        heap_adjust(data, i, len(data))

    
     #  从堆树中 [出栈] 排序输出
     #  测试数据 [5, 4, 3, 2]
    data[0], data[ - 1 ]  =  data[ - 1 ], data[0]
     for  n  in  range(len(data)  -   1 ,  1 ,  - 1 ):
        heap_adjust(data,  1 , n)
        data[0], data[n  -   1 ]  =  data[n - 1 ], data[0]



data = [ 2 , 3 , 6 , 3 , 868 , 9 , 8 , - 1 ]
heap_sort(data)
print  data
#  [-1, 2, 3, 3, 6, 8, 9, 868]