堆排序
要了解堆排序，先看什么是堆。如果一个序列，元素之间符合堆序，就叫做堆，所谓堆序就是：E[i]>=E[2i] 并且E[i]>=E[2i+1]，或者是E[i]<=E[2i] 并且E[i]<=E[2i+1]，注意这里的下标i是从1开始的。如[9,5,8,3,2,7,6]就是堆序的。第一个元素(9)比第二第三个大，第二个元素(5)比第四第五个大，第三个元素(8)比第六第七个小,…。
上面的例子，前面元素比后面大，说明最大的在序列开头，叫Max-Heap；如果前面比后面小，说明最小的在序列开头，叫Min-Heap，
从概念上，堆对应一棵完全二叉树，我们后面会学到树，父节点的值总是比子节点要大(或者小)。如果序列下标从0开始算，则节点i的左子节点位置为2i+1，右子节点位置为2i+2，而反过来算子节点i的父节点在位置(i-1)//2。
堆排序的基础是基于堆进行排序，假设手头有了一个堆，然后按照下面步骤进行循环：拿第一个元素(对max-heap就是最大元素)，将剩下的元素重新建成堆。
我们看拿掉第一个元素后，怎么才能让剩下的元素仍然是一个堆。
既然第一个元素被拿掉了，那么这个位置(根)就空出来了，我们就用最后的那个元素填到这个空位置来。这样的效果肯定是不再满足堆序了。按下面的规则进行调整：我们比较空位置和与其所对应的子节点的值（可能有两个子节点，我们取值大的那个子节点），当空节点的值比子节点的值要小的时候，就把空节点和子节点所对应的值交换。之后再从被交换的子节点位置处继续这么循环比较，直到节点大于子节点值，或者是找到序列的末尾了。
我们以堆序列[9,5,8,3,2,7,6]为例，思维上可以把它理解为这么一棵树：
这是一棵事先创建好的Max-Heap堆。我们先拿出第一个元素也是最大的元素9，堆变成这样子：
根成了空位置，我们用最后一个元素6填空，得到如下堆：
元素6填到空位置后，堆序破坏了。我们看一下空位置6的子节点，左子节点为5，右子节点为8，根据算法，我们确定要处理8，跟空位置比较，6比8小，所以交换，得到如下的堆：
然后当前位置就变成了6这个新位置了，再次比较，元素6只有一个左子节点7，6比7小，再次交换，得到如下堆：
然后当前位置就变成了6这个新位置了，再看，已经到了序列末尾了，停止。
调整完毕。
如果我们再拿第一个元素，这个时候是8，序列中除了前次拿掉的9之外最大的元素。一直循环拿N次，每次都是拿到了剩下的最大的那个值，拿完空出位置后跟最后一个交换之后再调整。这样就完成了排序。
看一下调整堆的代码：
def adjust(serial, start, end):
while True:
#找到值大的子节点node
lchild = 2 * start + 1
rchild = 2 * start + 2
node=lchild
if lchild > end: #到了末尾，终止
break
if rchild <= end and serial[lchild] < serial[rchild]:
node = rchild
#如果根小于子节点node，交换
if serial[start] < serial[node]:
serial[start], serial[node] = serial[node], serial[start]
#在新节点位置继续循环
start = node
else:#大于，终止
break
serial是堆序列，start是要调整的起始节点，end是序列末尾。
通过这个调整函数，排序过程就简单了：
def heapsort(serial):
for i in range(len(serial) - 1, 0, -1): #对堆中所有元素
print(serial[0]) #打印第一个元素，也即最大的元素
serial[0], serial[i] = serial[i], serial[0] #交换最后一个值
adjust(serial, 0, i - 1) #调整，末尾为i-1，相当于拿出了最大值缩短了序列
return serial
我们现在解决了排序的问题，还要回头来看最初怎么能创建出一个堆来。
我们看到了调整函数其实是把一棵子树调整为堆序，所以，利用调整函数，我们把序列的前半部分数据挨个调整一遍就可以了。
def buildheap(serial):
for i in range((len(serial) - 2) // 2, -1, -1): #调整前半部分数据
adjust(serial, i, len(serial) - 1)
return serial
我们测试一下：
serial = [3,5,7,2,6,8]
print(buildheap(serial))
print(heapsort(serial))
运行结果：
[8, 6, 7, 2, 5, 3]
[2, 3, 5, 6, 7, 8]
这就是堆排序。我们分析一下它的性能，堆排序经过两步，第一步创建堆，第二步排序。两步里面都要用到堆调整，而调整的性能与树的深度有关，为Log(N)。创建堆需要循环一半的数据，所以性能为N/2Log(N)，排序要处理所有数据，所以性能为NLog(N)，合在一起性能为N*Log(N)。
堆排序由Turing奖得主著名计算机科学家Floyd发明。他本来是芝加哥大学文学士，因为找不到工作就去当计算机操作员，后来自学成才。