堆排序过程
建立大顶堆或者小顶堆，大顶堆（一种二叉树型结构，子树节点值都小于父节点的值）。这个过程的要点是：先从最后一个非叶子节点开始构建堆，因为最后一个非叶子节点才有可能需要调整，然后向前查找的节点都有子树，都有可能需要调整。排序过程。建立好了大顶堆，那么第一个节点，肯定是所有节点中值最大的节点，所以把第一个节点和最后一个节点值互换。那么最大的节点就在最后了。这个时候需要重新调整的节点为第一个节点，而不需要像构建大顶堆那样从最后一个非叶子节点开始，因为除了第一个节点以外，其他的节点都是子树节点小于父节点，所以是Max_Heapify(heap,0,i)，树长度为n-1，因为最后一个节点为最大节点，不需要再调整了，否则又会调整到第一个节点了。
代码实现
def Max_Heapify(heap
, root
, n
):
left
= 2 * root
+ 1
right
= left
+ 1
if left
< n
and heap
[left
] > heap
[root
]:
┆ heap
[left
], heap
[root
] = heap
[root
], heap
[left
]
┆ Max_Heapify
(heap
,left
, n
)
if right
< n
and heap
[right
] > heap
[root
]:
┆ heap
[right
], heap
[root
] = heap
[root
], heap
[right
]
┆ Max_Heapify
(heap
, right
, n
)
def Build_Heap(numlist
):
n
= len(numlist
)
for i
in range((n
//2 - 1),-1, -1):
┆ Max_Heapify
(numlist
, i
, n
)
def sort(heap
):
n
= len(heap
)
for i
in range(n
-1,-1, -1):
┆ heap
[0], heap
[i
] = heap
[i
], heap
[0]
┆ Max_Heapify
(heap
,0,i
)
heap
= [4,6,8,5,9]
Build_Heap
(heap
)
sort
(heap
)
print heap
参考： https://blog.csdn.net/minxihou/article/details/51850001 https://www.cnblogs.com/chengxiao/p/6129630.html
