首页 > 代码库 > 排序算法系列——堆排序
排序算法系列——堆排序
记录学习点滴，菜鸟成长记
堆排序引入了另一种算法设计技巧：使用一种我们称之为“堆”的数据结构来进行数据管理。
堆排序算是真正意义上的利用数据结构来求解数组排序的方法。
“插入排序”和“归并排序”可以看做是一种“计算机体力活”，体现的思想更多的是去模拟最简单的人类思维，比如插入排序过程中的比较，归并中子问题合并时的比较。
“堆排序”可以看做是“计算机脑力活”，他利用了一种结构化的语言来表达，这种结构化带来一些性质，比如左右孩子、比【堆大小的一半向下取整】大的下标都是叶节点不需要维护其最大堆性质等。这里数据结构的性质更多的可以看做是一种“工具”，利用工具来工作总是“更快”和“高大上”一点。
1.堆
数组描述成（二叉）堆时，可以看做是一个近似的完全二叉树，除了最底层外，该树是完全充满的。
表示堆的数组A包括两个属性，A.length数组长度和A.heapsize堆大小，此处满足0≤A.heapsize≤A.length，可能的情况是数组元素并没有全部构成堆。
其他概念包括父节点、左孩子、右孩子，即给定一个节点i，有
1 def PARENT(i):2 if i>1:3 return i/24 else:5 return i6 def LEFT(i):7 return 2*i8 def RIGHT(i):9 return 2*i+1
2.维护堆的性质
这里维护指的是使得根节点为LEFT(i)和RIGHT(i)都是最大堆，最大堆即指使得每个节点都大于其左右孩子，算法思想是使得A[i]的值在最大堆中“逐级下降”，从而使得整个堆所有节点保持最大堆性质。有
1 def MAXHEAPIFY(A,i,heapsize):#维护最大堆性质，heapsize表示堆的大小 2 l = LEFT(i) 3 r = RIGHT(i) 4 if i <= heapsize/2: 5 if l <= heapsize and A[l-1] > A[i-1]: 6 largest = l 7 else: 8 largest = i 9 if r <= heapsize and A[r-1] > A[largest-1]:10 largest = r11 if largest != i:12 A[i-1],A[largest-1] = A[largest-1],A[i-1]13 MAXHEAPIFY(A,largest,heapsize)
3.建堆
采用自底向上的方法将一个大小为n的数组A转换为最大堆。二叉树的性质决定从(n/2+1)开始，元素都是树的叶节点，每个叶节点都可以看做是包含一个元素的堆，可以看做是一个最大堆。对于其他所有非叶节点，依次维护其最大堆性质，有，
1 def BUILDMAXHEAP(A):2 heapsize = len(A)3 for i in range(heapsize/2,0,-1):#倒序循环4 MAXHEAPIFY(A,i,heapsize)
4.堆排序
堆排序的终极思想就是：因为维护了最大堆的性质，所以根节点是数组中最大值，建完的堆类似于一个倒序排列；每次将最大值（即序列第一个值）和序列最后一个值互换；互换后，继续维护前面n-1长度序列的最大堆性质，继续互换；……；最后，最大堆中只有根节点。
1 def HEAPSORT(A):2 BUILDMAXHEAP(A)3 length,heapsize = len(A),len(A)4 for i in range(length,1,-1):5 A[0],A[i-1] = A[i-1],A[0]6 heapsize = heapsize - 17 MAXHEAPIFY(A, 1, heapsize)