堆排序，学习笔记
目录
一、概念
二、堆排序的基本步骤
1. 构建初始堆：
2. 排序过程
三、示例
一、概念
堆排序是一种基于二叉堆数据结构的排序算法。二叉堆是一种完全二叉树，它分为两种类型：最大堆和最小堆。在最大堆中，每个节点的值都大于或等于它的子节点的值；在最小堆中，每个节点的值都小于或等于它的子节点的值。堆排序利用了堆的这种性质来实现排序
例如，对于一个最大堆，根节点的值是整个堆中的最大值。当我们要进行排序时，我们可以利用这个性质，每次将堆顶元素（最大值）取出，然后重新调整堆，使得剩余元素仍然保持堆的性质，如此反复，直到堆为空，就可以得到一个有序的序列
二、堆排序的基本步骤
1. 构建初始堆：
假设我们有一个数组arr，要将其构建成一个最大堆。首先，我们从最后一个非叶子节点开始调整堆。对于一个长度为n的数组，最后一个非叶子节点的索引是parent(n/2 - 1)，其中parent(i)表示节点i的父节点索引，计算公式为parent(i)=(i - 1)/2。
对于每个非叶子节点，我们比较它和它的子节点的值。如果它小于子节点的值，就将它和最大的子节点交换位置，然后继续向下调整，直到满足堆的性质。例如，对于节点i，它有左子节点2i + 1和右子节点2i+2（如果存在），我们比较arr[i]、arr[2i + 1]和arr[2i + 2]的值，将arr[i]与最大的子节点交换位置。
2. 排序过程
当构建好初始堆后，堆顶元素就是数组中的最大值。我们将堆顶元素arr[0]与数组的最后一个元素arr[n - 1]交换位置，此时最大值就被放到了数组的末尾。
然后，我们将剩下的n - 1个元素重新构建成一个堆，因为此时堆顶元素可能不满足堆的性质了。我们再次从根节点开始调整堆，使得剩余元素仍然是一个最大堆。
重复上述交换和调整堆的步骤，每次将当前堆中的最大值放到数组的已排序部分的末尾，直到整个数组都被排序。
三、示例
def heapify(arr, n, i):largest = il = 2 * i + 1r = 2 * i + 2if l < n and arr[l] > arr[largest]:largest = lif r < n and arr[r] > arr[largest]:largest = rif 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[0], arr[i] = arr[i], arr[0]heapify(arr, i, 0)return arrarr = [12, 11, 13, 5, 6]
sorted_arr = heap_sort(arr)
print("排序后的数组:", sorted_arr) 在这个示例中，heapify函数用于调整堆，heap_sort函数用于实现整个堆排序的过程。首先通过heapify函数构建最大堆，然后通过交换堆顶元素和数组末尾元素，并重新调整堆的方式实现排序