Python排序搜索基本算法之堆排序实例详解


            本文实例讲述了Python排序搜索基本算法之堆排序。分享给大家供大家参考，具体如下：

堆是一种完全二叉树，堆排序是一种树形选择排序，利用了大顶堆堆顶元素最大的特点，不断取出最大元素，并调整使剩下的元素还是大顶堆，依次取出最大元素就是排好序的列表。举例如下，把序列[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]







前面的输出是不断取出最大元素后的大顶堆，由于是完全二叉树，根据列表可以自己写出大顶堆的树形结构，就不在这里赘述，最后一行是排好序的列表。

下面是堆排序算法，代码如下：





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)







输出如下：





[1, 5, 11, 15, 19, 26, 48, 59, 61, 77]







PS：这里再为大家推荐一款关于排序的演示工具供大家参考：

在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具：

http://tools.zwyuanma.com/aideddesign/paixu_ys

更多关于Python相关内容感兴趣的读者可查看本站专题：《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》

希望本文所述对大家Python程序设计有所帮助。