堆结构
最大堆: 父节点的值大于等于其子节点的值 最小堆: 父节点的值小于等于其子节点的值 本文以最大堆为例。
堆中最重要的操作为向上调整和向下调整。
-
向上调整（Heapify Up）：将一个节点向上移动，直至其父节点的值小于等于其子节点的值。 0-based 数组下标时，i 的父节点为 (i-1)/2。
-
向下调整（Heapify Down）：将一个节点向下移动，直至其子节点的值都小于等于其父节点的值。 0-based 数组下标时，i 的左子节点为 2i+1，右子节点为 2i+2。
1. 插入（Insert）
步骤：
1. 将新元素添加到数组末尾（完全二叉树的最后一个位置）。
2. 向上调整（Heapify Up）：将新元素与父节点比较，若不满足堆属性则交换，重复此过程直至根节点或满足属性。
- 时间复杂度：$O(log n)$（树的高度为 log n）。
1 2 3 4 5 6 7 8 9 10 11
void heap_insert(int arr[], int n, int key){ int i = n; arr[i] = key; int fa = (i - 1) / 2; while (arr[i] > arr[fa]) { swap(arr[i], arr[fa]); i = fa; fa = (i - 1) / 2; } }
2. 修改堆顶元素
步骤：
1. 将新元素代替为堆顶元素。
2. 向下调整（Heapify Down）：将堆顶元素与其子节点比较，若不满足堆属性则交换，重复此过程直至叶节点或满足属性。
- 时间复杂度：$O(log n)$（树的高度为 log n）。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
void heap_modify(int arr[], int n, int i) { while (1) { int max = i; // 每次循环重新计算子节点坐标 int lchil = 2 * i + 1; int rchil = 2 * i + 2; if (lchil < n && arr[lchil] > arr[max]) { max = lchil; } if (rchil < n && arr[rchil] > arr[max]) { max = rchil; } if (max == i) { break; } swap(arr[i], arr[max]); i = max; // 更新当前位置 } }
堆排序
步骤：
1. 构造最大堆 $O(n log n)$。
2. 交换堆顶元素与当前堆的最后一个元素（将最大值归位）。
3. 重复步骤 2，直至堆大小为 1。
- 时间复杂度：$O(n log n)$。
1 2 3 4 5 6 7 8 9 10 11 12
void heap_sort(int arr[], int n){ // 自顶向下（逐个插入）：O(nlogn) for(int i = 0; i < n; i++){ heap_insert(arr, n, arr[i]); // 向上调整 构造最大堆 } int size = n; while(size > 1){ swap(arr[0], arr[size - 1]); // 交换堆顶元素与最后一个元素 size--; // 堆的大小减一 heap_modify(arr, size, 0); // 向下调整 } }
优化： 自顶向下 $O(n log n)$ -> 自底向上建堆 $O(n)$ 堆排序 $O(n log n)$ 步骤：
- 构造最大堆 $O(n)$。
- 交换堆顶元素与当前堆的最后一个元素（将最大值归位）。
- 重复步骤 2，直至堆大小为 1。
- 时间复杂度：$O(n log n)$。
1 2 3 4 5 6 7 8 9 10 11 12 13
void heap_sort(int arr[], int n) { // 自底向上（Floyd算法）：O(n) for (int i = (n - 1 - 1) / 2; i >= 0; i--) { // i从最后一个非叶子节点(最后一个节点的父节点)开始向上建堆 heap_modify(arr, n, i); // 向下调整 构建最大堆 } int size = n; while (size > 1) { swap(arr[0], arr[size - 1]); // 交换堆顶元素与最后一个元素 size--; // 堆的大小减一 heap_modify(arr, size, 0); // 向下调整 } }
