"""
堆排序
"""
def heapify(arr, n, i):
largest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and arr[i] < arr[l]:
largest = l
if r < n and arr[largest] < arr[r]:
largest = r
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)
return arr
arr = [64, 34, 25, 12, 22, 11, 90]
print(heapSort(arr))
这段代码实现的是经典的**堆排序**算法。堆排序是一种基于比较的排序算法，它利用了二叉堆这种数据结构的特性来进行排序。
下面我将从代码含义、实现原理、用途和注意事项四个方面为您详细解释：
### 一、 代码含义逐行解析
1. *heapify(arr, n, i) 函数**：
- 作用：调整以 i 为根节点的子树，使其满足最大堆的性质（父节点的值大于或等于其左右子节点的值）。
- n 是堆的有效大小i 是当前需要调整的节点索引。
- l = 2 i + 1 和 r = 2 i + 2 分别计算左子节点和右子节点的索引（基于0起始的数组下标）。
- 接下来的两个 if 语句：找出当前节点、左子节点和右子节点中的最大值，并将其索引记录在 largest 中。
- 如果 largest != i，说明子节点比父节点大，违反了最大堆的性质。此时交换 arr[i] 和 arr[largest]，并**递归**调用 heapify 对交换后的子树继续调整，因为交换可能会破坏子树的原有堆结构。
2. *heapSort(arr) 函数**：
- 第一步：构建最大堆
- for i in range(n // 2 - 1, -1, -1): 从最后一个非叶子节点（索引为 n//2 - 1）开始，从下往上、从右往左依次调用 heapify，将整个无序数组构建成一个最大堆。
- 第二步：排序
- for i in range(n - 1, 0, -1): 从数组的最后一个位置开始向前遍历。
- arr[i], arr[0] = arr[0], arr[i] 将堆顶元素（当前最大值）与堆的最后一个未排序元素交换，这样最大值就到了它最终应该在的位置。
- heapify(arr, i, 0) 交换后，堆顶元素变小了，堆结构被破坏。此时对堆顶重新调用 heapify，范围限制在 i（即排除掉已经排好序的末尾元素），使其重新成为最大堆。
### 二、 实现原理
堆排序的核心思想是利用**完全二叉树**的性质：
1. 最大堆：树中每个节点的值都大于或等于其左右子节点的值，因此**堆顶元素（根节点）就是数组的最大值**。
2. 排序过程：
- 先将无序数组构建成最大堆。
- 取出堆顶的最大值，将其与数组末尾元素交换，此时末尾元素就位。
- 将堆的有效长度减1，对新的堆顶进行下沉操作heapify），恢复最大堆性质。
- 重复上述“交换-下沉”过程，直到堆中只剩一个元素，排序完成。
### 三、 用途
1. 大数据量排序：堆排序的时间复杂度稳定为 $O(n \log n)$，且空间复杂度为 $O(1)$，适合处理大规模数据的排序。
2. Top-K 问题：如果只需要找出数组中最大（或最小）的前 K 个元素，不需要完全排序，使用堆排序（或优先队列/堆结构）是非常高效的。只需构建堆后提取 K 次堆顶即可，时间复杂度为 $O(n + K \log n)$。
3. 内存受限的场景：相比于归并排序需要 $O(n)$ 的额外空间，堆排序是原地排序，非常适合在内存有限的嵌入式系统或大型数据文件处理中使用。
### 四、 注意事项
1. 不稳定性：堆排序是**不稳定**的排序算法。因为在堆调整过程中，相等的元素可能会因为节点的下沉和交换而改变相对顺序。例如，原数组中有两个相同的值，一个在父节点，一个在远处子节点，调整过程中子节点可能会被换到前面。
2. 缓存不友好：堆排序在访问数组元素时，跳跃性很大（如从索引 0 跳到 2，再到 6 等），这导致空间局部性差，CPU 缓存命中率低。因此，在实际运行速度上，堆排序往往比同样时间复杂度的快速排序慢。
3. 递归深度：代码中的 heapify 使用了递归实现。虽然对于完全二叉树而言，递归深度为 $O(\log n)$，通常不会引发栈溢出，但在极端追求性能或内存极度受限的环境下，可以将其改写为迭代（循环）实现以减少函数调用的开销。
4. 边界条件：代码中 l < n 和 r < n 的判断非常关键，它确保了不会访问越界的数组元素，特别是在构建堆和排序后期堆的大小逐渐缩小时。