堆排序学习笔记及堆排序算法的python实现
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。
堆排序是一种选择排序，其时间复杂度为O(nlogn).
堆的定义
n个元素的序列{k1，k2，…,kn}当且仅当满足下列关系之一时，称之为堆。
情形1：ki <= k2i 且ki <= k2i+1 （最小化堆或小顶堆）
情形2：ki >= k2i 且ki >= k2i+1 （最大化堆或大顶堆）
其中i=1,2,…,n/2向下取整;
堆可以看成是一个完全二叉树。完全二叉树中所有非终端结点的值均不大于（或不小于）其左右孩子结点的值。堆顶元素（完全二叉树的根）必为序列中的最大或最小值。
若在输出堆顶的最小值之后，使得剩余n-1个元素的序列重又建成一个堆，则得到n个元素的次小值。如此反复执行，便能得到一个有序序列，这个过程称之为堆排序。
堆排序（Heap Sort）只需要一个记录元素大小的辅助空间（供交换用），每个待排序的记录仅占有一个存储空间。
堆的存储：
一般用数组表示堆，若根结点存在序号0处， i结点的父结点下标就为(i-1)/2。i结点的左右子结点下标分别为2*i+1和2*i+2。（注：如果根结点是从1开始，则左右孩子结点分别是2i和2i+1。）
堆排序的实现
实现堆排序需要解决两个问题：
1、如何由一个无序序列建成一个堆？
2、如何在输出堆顶元素之后，调整剩余元素成为一个新的堆。
对于第二个问题，一般在输出堆顶元素之后，视为将这个元素排除，然后用表中的最后一个元素填补它的位置，自下向上调整：首先，将堆顶元素和它的左右子树的根节点进行比较，把最小的元素交换到堆顶；然后，顺着被破坏的路径一路调整下去，直至叶子节点，就得到新的堆。我们称这个自堆顶至叶子的调整过程为“筛选”。
构造初始堆
给定一个数组，首先，根据该数组元素构造一个完全二叉树；然后，从最后一个非叶子结点开始，每次都是从父结点、左孩子、右孩子中进行比较交换，交换可能会引起孩子结点不满足堆的性质，所以每次交换之后需要重新对被交换的孩子结点进行调整。
进行堆排序
其基本思想为(大顶堆)：
1)将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆，此堆为初始的无序区；
2)将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn),且满足R[1,2...n-1]<=R[n];
3)由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
实例：
此处是参照一篇博客总结的，大致内容都是这个博客中的（堆排序 Heap Sort）。
1.初始的堆结构
2.交换堆顶的元素和最后一个元素，此时最后一个位置作为有序区（有序区显示为***），然后进行其他无序区的堆调整，重新得到大顶堆后，交换堆顶和倒数第二个元素的位置……
想得到升序，则建立大顶堆，若想得到降序，则建立小顶堆。
堆排序分析
堆排序方法对记录数较少的文件并不值得提倡，但对n较大的文件还是很有效的。因为其运行时间主要耗费在建初始堆和调整建新堆时进行的反复“筛选”上。
堆排序在最坏的情况下，其时间复杂度也为O(nlogn)。相对于快速排序来说，这是堆排序的最大优点。此外，堆排序仅需一个记录大小的供交换用的辅助存储空间。
python代码实现：
def fixDown(a,k,n): #自顶向下堆化，从k开始堆化
N=n-1
while 2*k<=N:
j=2*k
if j<N and a[j]<a[j+1]: #选出左右孩子节点中更大的那个
j+=1
if a[k]<a[j]:
a[k],a[j]=a[j],a[k]
k=j
else:
break
def heapSort(l):
n=len(l)-1
for i in range(n//2,0,-1):
fixDown(l,i,len(l))
while n>1:
l[1],l[n]=l[n],l[1]
fixDown(l,1,n)
n-=1
return l[1:]
l=[-1,26,5,77,1,61,11,59,15,48,19] #第一个元素不用，占位
res=heapSort(l)
print(res)转载于:https://blog.51cto.com/jx610/1702260