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

---

💝💝💝欢迎莅临我的博客，很高兴能够在这里和您见面！希望您在这里可以感受到一份轻松愉快的氛围，不仅可以获得有趣的内容和知识，也可以畅所欲言、分享您的想法和见解。

• 推荐：「stormsha的主页」👈，「stormsha的知识库」👈持续学习，不断总结，共同进步，为了踏实，做好当下事儿~

• 专栏导航

  • Python系列: Python面试题合集，剑指大厂
  • Git系列: Git操作技巧
  • GO系列: 记录博主学习GO语言的笔记，该笔记专栏尽量写的试用所有入门GO语言的初学者
  • 数据库系列: 详细总结了常用数据库 mysql 技术点,以及工作中遇到的 mysql 问题等
  • 运维系列: 总结好用的命令，高效开发
  • 算法与数据结构系列: 总结数据结构和算法,不同类型针对性训练,提升编程思维

  非常期待和您一起在这个小小的网络世界里共同探索、学习和成长。💝💝💝 ✨✨ 欢迎订阅本专栏 ✨✨

  💖The Start💖点点关注，收藏不迷路💖

---

堆排序（Heap Sort）是一种基于堆数据结构的比较排序算法。堆是一种特殊的完全二叉树结构，分为最大堆和最小堆。最大堆的特点是每个节点的值都大于或等于其子节点的值，最小堆则相反。

堆排序的基本思想是将数组构造成一个堆，然后利用堆的特性不断调整堆结构，将最大（或最小）值移到数组的末尾，从而实现排序。

堆排序的步骤

1. 构建最大堆：将未排序的数组构造成最大堆。
2. 交换堆顶元素和末尾元素：将最大堆的堆顶元素（即最大值）与末尾元素交换，然后将堆的大小减1。
3. 调整堆：调整堆结构使其再次成为最大堆。
4. 重复步骤2和步骤3，直到堆的大小为1。

代码实现

以下是堆排序的Python实现：

def heapify(arr, n, i):"""将以i为根的子树调整为最大堆:param arr: 数组:param n: 堆的大小:param i: 根节点索引"""largest = i  # 初始化最大值节点为根节点left = 2 * i + 1  # 左子节点right = 2 * i + 2  # 右子节点# 如果左子节点存在且大于根节点，则更新最大值节点if left < n and arr[left] > arr[largest]:largest = left# 如果右子节点存在且大于根节点，则更新最大值节点if right < n and arr[right] > arr[largest]:largest = right# 如果最大值不是根节点，则交换并继续调整堆if largest != i:arr[i], arr[largest] = arr[largest], arr[i]heapify(arr, n, largest)def heapSort(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)# 测试
arr = [12, 11, 13, 5, 6, 7]
heapSort(arr)
print("排序后的数组：", arr)

详细说明

1. heapify函数：用于调整以索引i为根的子树，使其满足最大堆的性质。通过比较根节点和左右子节点的大小，找出最大值节点，并进行必要的交换。递归地调整交换后的子树。

2. heapSort函数：

   • 构建最大堆：从最后一个非叶子节点开始，逐步向上调整每个子树，使整个数组成为一个最大堆。
   • 排序：逐个将堆顶（最大值）元素与末尾元素交换，并缩小堆的大小，然后调整堆以保持最大堆性质。

时间复杂度和空间复杂度

• 时间复杂度：堆排序的时间复杂度为O(n log n)，因为构建堆的时间复杂度为O(n)，调整堆的时间复杂度为O(log n)，在最坏情况下需要进行n次调整。
• 空间复杂度：堆排序是原地排序算法，空间复杂度为O(1)。

应用场景

堆排序适用于需要稳定时间复杂度且对空间复杂度要求较高的应用场景。虽然堆排序的最坏情况下时间复杂度与快速排序相同，但其在实际应用中可能不如快速排序高效。

总结

堆排序是一种高效的比较排序算法，通过利用堆数据结构的特性，能够在O(n log n)的时间内完成排序。理解堆排序的基本思想和实现步骤，对于深入学习排序算法和数据结构具有重要意义。

---

🔥🔥🔥道阻且长,行则将至,让我们一起加油吧！🌙🌙🌙

💖The End💖点点关注，收藏不迷路💖