数据结构堆
- 是一颗完全二叉树。完全二叉树：设二叉树的深度为h，除了第h层以外，前面的每一层的节点数都达到最大，并且第h层的叶子都集中在最左边。
- 所有非终端（有叶子）节点的值均不小于（或不大于）其左、右孩子的值。前者叫大顶堆，后者叫小顶堆。
堆排序思想
利用堆数据结构的堆顶肯定是最大值（或最小值），则可以取出堆顶元素，然后对剩下的元素重新构造大顶堆（或小顶堆）后，继续取出堆顶元素，知道所有元素被取完。则取出的元素会按照顺序排列。
图解堆排序过程
alist = [16,7,3,20,17,8]为例
-
首先根据列表构造一个完全二叉树
来自百度百科.png -
构造初始堆，从叶子节点往上层调整
来自百度百科.png -
发现20和16交换位置后，不满足堆的性质，所以重新调整
来自百度百科.png -
这样就得到了大顶堆，让堆顶元素和最后一个叶子节点交换位置
来自百度百科.png -
排除元素20后，重新构造堆结构。直到所有元素排除完。
来自百度百科.png
来自百度百科.png
python实现
#!/usr/bin/python
# encoding: utf-8
# 从start到end的位置构造一个大顶堆
def siftAdjust(alist, start, end):
# start位置作为堆顶
root = start
# 左叶子
while True:
# child初始为左边的子节点
child = root * 2 + 1
if child >= end:
break
# 比较左右叶子节点的大小，找出最大的那一个
if child + 1 <= len(alist) - 1 and alist[child] < alist[child + 1]:
child = child + 1
# 把最大的子节点和根节点交换位置
if alist[root] < alist[child]:
alist[root], alist[child] = alist[child], alist[root]
# 调整过后，需要更新根节点，以防交换位置后，子树不再是堆结构
root = child
# 若没有调整，则直接退出
else:
break
def heapSort(alist):
# 从最后一个有子节点的位置开始调整大顶堆
first = (len(alist) - 2) // 2
# 初始化一个大顶堆
for i in range(first, -1, -1):
siftAdjust(alist, i, len(alist) - 1)
# 第i趟排序
for i in range(len(alist)-1,0,-1):
# 把第一个位置堆顶与最后一个位置交换
alist[0],alist[i] = alist[i],alist[0]
# 调整堆结构
siftAdjust(alist,0,i-1);
if __name__ == '__main__':
a = [4,10,7,9,5,3,1,2,8,6]
heapSort(a)
print(a)
