本文實(shí)例講述了Python排序搜索基本算法之堆排序。分享給大家供大家參考，具體如下：
堆是一種完全二叉樹，堆排序是一種樹形選擇排序，利用了大頂堆堆頂元素最大的特點(diǎn)，不斷取出最大元素，并調(diào)整使剩下的元素還是大頂堆，依次取出最大元素就是排好序的列表。舉例如下，把序列[26,5,77,1,61,11,59,15,48,19]排序，如下：
基于堆的優(yōu)先隊(duì)列算法代碼如下：
def fixUp(a): #在堆尾加入新元素，fixUp恢復(fù)堆的條件 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//2def fixDown(a): #取a[1]返回的值，然后把a(bǔ)[N]移到a[1]，fixDown來恢復(fù)堆的條件 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: breakdef 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 maxElemdata=[-1,] #第一個(gè)元素不用，占位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)-1for i in range(N): print(data) result.append(delMax(data))print(result)fixUp函數(shù)用于向列表的尾部添加一個(gè)新的元素，然后調(diào)整成大頂堆；fixDown函數(shù)用于取出大頂堆最大的元素后，把列表尾部的元素放到堆頂位置，然后再調(diào)整成大頂堆；insert函數(shù)是每次插入一個(gè)新的元素并調(diào)整成為大頂堆；delMax函數(shù)把最大的元素返回出來并把剩下的元素調(diào)整成為大頂堆。
輸出如下：
[-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]
前面的輸出是不斷取出最大元素后的大頂堆，由于是完全二叉樹，根據(jù)列表可以自己寫出大頂堆的樹形結(jié)構(gòu)，就不在這里贅述，最后一行是排好序的列表。
下面是堆排序算法，代碼如下：
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]: #選出左右孩子節(jié)點(diǎn)中更大的那個(gè) j+=1 if a[k]<a[j]: a[k],a[j]=a[j],a[k] k=j else: breakdef 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] #第一個(gè)元素不用，占位res=heapSort(l)print(res)
新聞熱點(diǎn)
疑難解答
圖片精選
