Python堆排序算法实现与原理详解

凌晨两点半

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

原创

本文详细介绍Python中堆排序算法的实现原理与代码示例。通过构建完全二叉树并调整为大顶堆，逐步交换根节点与末尾元素完成排序。文中提供完整Python代码及在线演示工具链接，适合希望深入理解排序算法的开发者参考。

本文分享一个使用Python实现的堆排序算法示例，供读者参考学习。

堆排序的核心思想基于堆这种数据结构。堆可以被视为一棵完全二叉树，其特性是任意非叶子节点的值都不大于（或不小于）其左右子节点的值。排序过程首先将无序序列调整为堆结构，从而确定序列的最大值（或最小值）。随后将该极值交换至序列末尾，使有序序列元素增加一个，无序序列元素减少一个。对剩余无序部分重复此调整与交换操作，即可完成排序。

堆排序的具体执行步骤如下：

1. 从无序序列对应的完全二叉树的第一个非叶子节点开始，按照从右至左、从下至上的顺序对每个节点进行调整，最终构建出一个大顶堆。

节点调整的具体方法为：比较当前节点（设为a）与其子节点的值。若存在大于a的子节点，则选取其中最大的一个与a进行交换。交换后，a下沉至下一层，重复上述比较与交换过程，直到a的子节点值均小于a为止。

2. 将当前无序序列的第一个元素（即树根节点b）与无序序列的最后一个元素（设为c）交换。此时，b进入有序序列并到达最终位置。无序序列元素数量减1，有序序列元素数量加1。由于c被交换到根位置，可能不再满足堆的定义，因此需要对c进行调整。

3. 重复步骤2的操作，直到无序序列中仅剩一个元素时，排序结束。

# -*- coding:utf-8 -*-
# 堆排序适用于记录数很多的情况
from collections import deque
# 这里需要说明元素的存储必须要从1开始
# 涉及到左右节点的定位，和堆排序开始调整节点的定位
# 在下标0处插入0，它不参与排序
L = deque([49,38,65,97,76,13,27,49])
L.appendleft(0)
#L = [0,49,38,65,97,76,13,27,49]
def element_exchange(numbers,low,high):
  temp = numbers[low]
  # j 是low的左孩子节点(cheer!)
  i = low
  j = 2*i
  while j<=high:
    # 如果右节点较大，则把j指向右节点
    if j<high and numbers[j]<numbers[j+1]:
      j = j+1
    if temp<numbers[j]:
      # 将numbers[j]调整到双亲节点的位置上
      numbers[i] = numbers[j]
      i = j
      j = 2*i
    else:
      break
  # 被调整节点放入最终位置
  numbers[i] = temp
def top_heap_sort(numbers):
  length = len(numbers)-1
  # 指定第一个进行调整的元素的下标
  # 它即该无序序列完全二叉树的第一个非叶子节点
  # 它之前的元素均要进行调整
  # cheer up！
  first_exchange_element = length/2
  #建立初始堆
  print first_exchange_element
  for x in range(first_exchange_element):
    element_exchange(numbers,first_exchange_element-x,length)
  # 将根节点放到最终位置，剩余无序序列继续堆排序
  # length-1 次循环完成堆排序
  for y in range(length-1):
    temp = numbers[1]
    numbers[1] = numbers[length-y]
    numbers[length-y] = temp
    element_exchange(numbers,1,length-y-1)
if __name__=='__main__':
  top_heap_sort(L)
  for x in range(1,len(L)):
    print L[x],

运行结果展示如下：