堆排序算法

题目描述：
堆排序是一种基于二叉堆（完全二叉树）数据结构的高效排序算法。它利用堆的性质（最大堆或最小堆）来对数组进行排序。题目要求你理解堆排序的原理，并能够用代码实现它。

解题过程：

1. 理解堆的性质：

   • 堆是一种完全二叉树，分为最大堆和最小堆。
     • 最大堆：每个父节点的值都大于或等于其子节点的值（根节点最大）。
     • 最小堆：每个父节点的值都小于或等于其子节点的值（根节点最小）。
   • 堆排序通常使用最大堆进行升序排序（最小堆用于降序排序）。
   • 在数组中，堆的节点关系可通过索引表示：
     • 父节点索引 i 的左子节点索引为 2*i + 1。
     • 父节点索引 i 的右子节点索引为 2*i + 2。
     • 子节点索引 i 的父节点索引为 (i-1)/2（向下取整）。

2. 堆排序的步骤：
   堆排序分为两个主要阶段：建堆（Heapify）和排序。

   • 建堆：将无序数组调整为一个最大堆。
   • 排序：重复将堆顶元素（最大值）与堆末尾元素交换，并重新调整堆，直到整个数组有序。

3. 逐步拆解实现：
   步骤1：实现堆调整函数（Heapify）

   • 作用：以某个节点为根，调整其子树使其满足最大堆性质。
   • 过程：
     1. 假设当前节点 i 为最大值。
     2. 比较其与左右子节点的值，找到最大值对应的索引。
     3. 如果最大值不是当前节点，则交换节点值，并递归调整被交换的子节点所在的子树。
   • 示例代码（以最大堆为例）：

     def heapify(arr, n, 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)  # 调整被交换的子节点
     

   步骤2：建堆（从最后一个非叶子节点开始）

   • 完全二叉树中，最后一个非叶子节点的索引为 n//2 - 1（n 为数组长度）。
   • 从后向前遍历所有非叶子节点，对每个节点调用 heapify，确保整个数组满足最大堆性质。
   • 示例代码：

     def build_max_heap(arr):
         n = len(arr)
         # 从最后一个非叶子节点开始向前遍历
         for i in range(n//2 - 1, -1, -1):
             heapify(arr, n, i)
     

   步骤3：排序

   • 将堆顶元素（最大值）与当前堆的末尾元素交换，此时最大值已就位。
   • 缩小堆的范围（排除已排序元素），对新的堆顶元素进行调整，使其重新满足最大堆性质。
   • 重复直到堆中只剩一个元素。
   • 示例代码：

     def heap_sort(arr):
         n = len(arr)
         build_max_heap(arr)  # 先建堆
         # 从后向前遍历，交换堆顶和末尾元素
         for i in range(n-1, 0, -1):
             arr[0], arr[i] = arr[i], arr[0]  # 将最大值移到末尾
             heapify(arr, i, 0)  # 调整剩余堆（范围缩小为 i）
     

4. 完整代码示例：

   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[0], arr[i] = arr[i], arr[0]
           heapify(arr, i, 0)
   
   def heapify(arr, n, 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)
   
   # 测试
   arr = [12, 11, 13, 5, 6, 7]
   heap_sort(arr)
   print("排序结果:", arr)  # 输出 [5, 6, 7, 11, 12, 13]
   

5. 时间复杂度与空间复杂度：

   • 时间复杂度：建堆过程为 O(n)，排序过程为 O(n log n)，整体为 O(n log n)。
   • 空间复杂度：递归调用堆调整函数时使用栈空间，最坏情况下为 O(log n)，属于原地排序。

总结：
堆排序的关键在于理解堆的性质和调整过程。通过建堆和重复交换堆顶元素，逐步将最大值移动到数组末尾，最终实现排序。注意堆调整函数（Heapify）的递归或迭代实现方式，确保每一步都维护堆的性质。