堆排序详解(python实现)

1、堆的定义

满足以下情形的数据结构：

情形1：k_i <= k_2i 且k_i <= k_2i+1 （最小化堆或小顶堆：左、右子孩子的值比父结点的值都大）

情形2：k_i >= k_2i 且k_i >= k_2i+1 （最大化堆或大顶堆：左、右子孩子的值比父结点的值都小）

2、堆排序

一般从小到大的排序利用大顶堆实现。基本思想为：

1、将初始待排序关键字序列构建成大顶堆

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，则整个排序过程完成。

3、堆的生成

叶节点不用调整，首先应该从最后一个非子节点开始，即序号N/2-1节点。

def heapAdjust(a,i,n): while i*2+1<n: j = i*2+1 if j+1<n: if a[j+1]>a[j]: j += 1 t = a[i] if a[j]>t: a[i] = a[j] a[j] = t i = j else: break

从N/2-1节点向前调整，至此生成一个大顶堆。

i = length//2-1 a = tinput while i>=0: adjust(a,i,length) i-=1

4、堆排序

将堆顶和最后一个元素进行交换，然后对前面的元素进行调整。

t = a[0] a[0] = a[length-1] a[length-1] = t N = length-1 while N>0: heapAdjust(a,0,N) t = a[0] a[0] = a[N-1] a[N-1] = t N-=1

完整代码：

def adjust(a,i,n): while i*2+1 < n: j = i*2+1 t = a[j] if j+1<n: if a[j]<a[j+1]: t = a[j+1] j = j+1 if a[i]<a[j]: a[j] = a[i] a[i] = t i = j else: break i = length//2-1 a = tinput while i>=0: adjust(a,i,length) i-=1 t = a[0] a[0] = a[length-1] a[length-1] = t N = length-1 while N>0: adjust(tinput,0,N) t = a[0] a[0] = a[N-1] a[N-1] = t N-=1