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

陆遥

发布时间：2026-10-13| 3人浏览过

原创

本文深入解析Python中的堆排序算法，通过大顶堆特性演示排序过程。详细讲解了基于堆的优先队列实现，包括fixUp和fixDown函数的调整逻辑，以及完整的堆排序代码示例，帮助开发者掌握排序搜索基本算法。

本文详细介绍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)

运行输出结果如下：