堆（二插堆）
一、堆的基本概念
堆是一种基于完全二叉树的数据结构，并且满足堆序性质：
- 大顶堆（大根堆）：任意父节点的值 ≥ 子节点的值，堆顶为最大值。
- 小顶堆（小根堆）：任意父节点的值 ≤ 子节点的值，堆顶为最小值。
特点：
- 逻辑上是一棵完全二叉树
- 物理上可以用数组顺序存储
- 不要求中序有序，只要求父子有序
- 常用于排序、优先队列、TOP-K 问题等
二、堆的节点下标计算公式（数组从 0 开始）
对于数组中任意下标为i的节点：
- 左孩子下标：
child_left = 2 * i + 1 - 右孩子下标：
child_right = 2 * i + 2 - 父节点下标：
parent = (i - 1) / 2（整数除法）
最后一个非叶子节点
数组长度为n时：最后一个非叶子节点下标：last_non_leaf = (n - 2) / 2
堆排序建堆时，就是从这个位置自底向上调整。
三、堆排序核心思路
构建大顶堆从最后一个非叶子节点开始，向上逐个执行向下调整，使整个数组满足堆性质。
交换堆顶与末尾元素将堆顶最大值放到数组末尾，确定一个元素的最终位置。
重新调整堆结构排除已排好的末尾元素，对新堆顶再次向下调整，重复上述步骤直到整个数组有序。
四、时间复杂度
- 建堆：O(n)
- 排序：每次调整 O (log n)，共 n 次 →O(n log n)
- 整体时间复杂度：O(n log n)
- 空间复杂度：O(1)（原地排序）
堆排序不依赖数据初始顺序，最好、最坏、平均复杂度都是O(n log n)。
五、总结
- 堆 = 完全二叉树 + 堆序性质
- 数组存储，下标公式是核心
- 堆排序 = 建堆 + 交换堆顶 + 向下调整
- 高效稳定的排序算法，时间复杂度 O (n log n)，原地排序
堆排序：实现从小到大的排序 用大堆
void Heapsort(int* arr, int n) { for (int i = (n - 1 - 1) / 2; i >= 0; i--) {//从最下面的节点开始进行调整让后向上继续调整 int parent = i; int child = parent * 2 + 1; while (child < n) { if ((child + 1 < n) && arr[child] < arr[child + 1]) { child++; } if (arr[child] > arr[parent]) { swap(&arr[child], &arr[parent]); parent = child; child = parent * 2 + 1; } else { break; } } } int end = n - 1; while (end > 0) {//每次交换后我们要重新向下调整 swap(&arr[0], &arr[end]); int parent = 0;//从第一个开始 int child = parent * 2 + 1; while (child < end) { if ((child + 1 < end) && arr[child] < arr[child + 1]) { child++; } if (arr[child] > arr[parent]) { swap(&arr[child], &arr[parent]); parent = child; child = parent * 2 + 1; } else { break; } } end--;//当前最后一个值成为最大值 } }