【Python排序搜寻基本算法】之堆排序
【Python排序搜索基本算法】之堆排序
fixUp函数用于向列表的尾部添加一个新的元素,然后调整成大顶堆;fixDown函数用于取出大顶堆最大的元素后,把列表尾部的元素放到堆顶位置,然后再调整成大顶堆;insert函数是每次插入一个新的元素并调整成为大顶堆;delMax函数把最大的元素返回出来并把剩下的元素调整成为大顶堆。
前面的输出是不断取出最大元素后的大顶堆,由于是完全二叉树,根据列表可以自己写出大顶堆的树形结构,就不在这里赘述,最后一行是排好序的列表。
堆是一种完全二叉树,堆排序是一种树形选择排序,利用了大顶堆堆顶元素最大的特点,不断取出最大元素,并调整使剩下的元素还是大顶堆,依次取出最大元素就是排好序的列表。举例如下,把序列[26,5,77,1,61,11,59,15,48,19]排序,如下:
代码如下:
def fixUp(a): #在堆尾加入新元素,fixUp恢复堆的条件 k=len(a)-1 while k>1 and a[k//2]<a[k]: a[k//2],a[k]=a[k],a[k//2] k=k//2 def fixDown(a): #取a[1]返回的值,然后把a[N]移到a[1],fixDown来恢复堆的条件 k=1 N=len(a)-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 insert(a,elem): a.append(elem) fixUp(a) def delMax(a): maxElem=a[1] N=len(a) if N<=1: print('There\'s none element in the list') return -1 if N==2: return a[1] else: a[1]=a.pop() fixDown(a) return maxElem data=[-1,] #第一个元素不用,占位 insert(data,26) insert(data,5) insert(data,77) insert(data,1) insert(data,61) insert(data,11) insert(data,59) insert(data,15) insert(data,48) insert(data,19) result=[] N=len(data)-1 for i in range(N): print(data) result.append(delMax(data)) print(result)
fixUp函数用于向列表的尾部添加一个新的元素,然后调整成大顶堆;fixDown函数用于取出大顶堆最大的元素后,把列表尾部的元素放到堆顶位置,然后再调整成大顶堆;insert函数是每次插入一个新的元素并调整成为大顶堆;delMax函数把最大的元素返回出来并把剩下的元素调整成为大顶堆。
输出如下:
[-1, 77, 61, 59, 48, 19, 11, 26, 1, 15, 5] [-1, 61, 48, 59, 15, 19, 11, 26, 1, 5] [-1, 59, 48, 26, 15, 19, 11, 5, 1] [-1, 48, 19, 26, 15, 1, 11, 5] [-1, 26, 19, 11, 15, 1, 5] [-1, 19, 15, 11, 5, 1] [-1, 15, 5, 11, 1] [-1, 11, 5, 1] [-1, 5, 1] [-1, 1] [77, 61, 59, 48, 26, 19, 15, 11, 5, 1]
前面的输出是不断取出最大元素后的大顶堆,由于是完全二叉树,根据列表可以自己写出大顶堆的树形结构,就不在这里赘述,最后一行是排好序的列表。
转载请注明:转自http://blog.csdn.net/littlethunder/article/details/23877545