国产区在线视频观看,免费玖玖丝袜,综合二区拍

快捷導航

Python排序搜索基本算法之堆排序?qū)嵗斀?/h1>

更新時間：2017年12月08日 11:33:14 作者：littlethunder

這篇文章主要介紹了Python排序搜索基本算法之堆排序,結(jié)合實例形式詳細分析了堆排序的原理、Python實現(xiàn)方法及相關(guān)操作注意事項,需要的朋友可以參考下

本文實例講述了Python排序搜索基本算法之堆排序。分享給大家供大家參考，具體如下：

堆是一種完全二叉樹，堆排序是一種樹形選擇排序，利用了大頂堆堆頂元素最大的特點，不斷取出最大元素，并調(diào)整使剩下的元素還是大頂堆，依次取出最大元素就是排好序的列表。舉例如下，把序列[26,5,77,1,61,11,59,15,48,19]排序，如下：

基于堆的優(yōu)先隊列算法代碼如下：

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//2
def fixDown(a): #取a[1]返回的值，然后把a[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:
      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函數(shù)用于向列表的尾部添加一個新的元素，然后調(diào)整成大頂堆；fixDown函數(shù)用于取出大頂堆最大的元素后，把列表尾部的元素放到堆頂位置，然后再調(diào)整成大頂堆；insert函數(shù)是每次插入一個新的元素并調(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é)點中更大的那個
      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)

輸出如下：