当前位置：首页 > Python > 正文

Python堆排序算法详解 - 原理、实现与优化 | 算法教程

Python堆排序算法详解

全面解析堆排序原理，提供Python实现代码，包含可视化演示和复杂度分析

什么是堆排序？

堆排序（Heapsort）是一种基于二叉堆数据结构的比较排序算法。它由J.W.J. Williams在1964年发明。 堆排序具有原地排序和时间复杂度O(n log n)的特点。

堆排序基本原理

  • 将无序数组构建成二叉堆（最大堆或最小堆）
  • 将堆顶元素（最大值/最小值）与末尾元素交换
  • 减少堆长度，重新调整剩余元素为堆结构
  • 重复上述步骤直到堆长度为1

堆排序特点

  • 时间复杂度：O(n log n)
  • 空间复杂度：O(1)
  • 不稳定排序算法
  • 适合大数据量排序

Python堆排序实现

下面是完整的堆排序Python实现代码： 


def heapify(arr, n, i):
    """调整以i为根的子树为大顶堆"""
    largest = i  # 初始化最大元素为根
    left = 2 * i + 1
    right = 2 * i + 2

    # 如果左子节点存在且大于根
    if left < n and arr[i] < arr[left]:
        largest = left

    # 如果右子节点存在且大于当前最大值
    if right < n and arr[largest] < arr[right]:
        largest = right

    # 如果最大值不是根节点，则交换
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]  # 交换
        heapify(arr, n, largest)  # 递归调整子树

def heap_sort(arr):
    """堆排序主函数"""
    n = len(arr)
    
    # 构建最大堆（从最后一个非叶子节点开始）
    for i in range(n//2 - 1, -1, -1):
        heapify(arr, n, i)
    
    # 逐个提取元素
    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # 将当前最大值移到数组末尾
        heapify(arr, i, 0)  # 调整剩余元素为堆

# 测试堆排序
if __name__ == "__main__":
    data = [12, 11, 13, 5, 6, 7, 3, 16, 8]
    print("原始数组:", data)
    
    heap_sort(data)
    print("排序后数组:", data)

代码说明：

  • heapify函数：维护堆的性质，使以i为根的子树成为最大堆
  • heap_sort函数：堆排序主函数，先构建堆，然后逐步提取最大值
  • 构建堆：从最后一个非叶子节点开始向上调整
  • 排序过程：每次将堆顶元素（最大值）与末尾元素交换，然后调整剩余元素

堆排序过程可视化

当前步骤说明：

点击"下一步排序"按钮查看堆排序的每一步过程

堆排序复杂度分析

时间复杂度

堆排序的平均和最坏情况时间复杂度均为O(n log n)

构建堆：O(n)
每次调整堆：O(log n)
共调整n次：O(n log n)

空间复杂度

堆排序的空间复杂度为O(1)

原地排序算法
仅需常数级额外空间

稳定性

堆排序是不稳定的排序算法

交换操作可能改变相同元素的相对顺序
不适合需要稳定排序的场景

堆排序应用场景

1 大规模数据排序

当数据量很大时，堆排序的O(n log n)时间复杂度比O(n²)算法高效得多，适合处理百万级甚至更大规模的数据排序。

2 优先队列实现

堆结构是实现优先队列的理想选择，堆排序的核心操作（插入和提取最大值）与优先队列的操作完全一致。

3 内存受限环境

由于堆排序是原地排序算法，空间复杂度为O(1)，因此特别适合内存受限的环境（如嵌入式系统）中使用。

© 2023 Python算法教程 | 堆排序算法详解

本教程仅供学习参考，欢迎分享给其他Python开发者

本文由LianpoGan于2025-07-28发表在吾爱品聚，如有疑问，请联系我们。
本文链接：https://www.521pj.cn/20256692.html

相关文章

发表评论