知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 02 - 堆排序 ## 题目(LeetCode 912) 给你一个整数数组 `nums`,请你将该数组升序排列。 ``` 输入:nums = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7] 输出:[1, 2, 3, 4, 7, 8, 9, 10, 14, 16] ``` ## 先搞清楚:什么是堆 堆是一种**完全二叉树**(除了最后一层,其他层都是满的,最后一层从左到右填充),用数组就能存。 ``` 大顶堆(Max-Heap):父节点 ≥ 左右孩子 小顶堆(Min-Heap):父节点 ≤ 左右孩子 ``` ### 堆用数组存 ``` 16 / \ 14 10 / \ / \ 8 7 9 3 / \ / 2 4 1 数组表示:[16, 14, 10, 8, 7, 9, 3, 2, 4, 1] 索引: 0 1 2 3 4 5 6 7 8 9 下标 i 的节点: 父节点:(i - 1) / 2 左孩子:2 * i + 1 右孩子:2 * i + 2 ``` 记住这三个公式,堆操作就都能写了。 ## 大白话理解 升序排序用**大顶堆**。核心思路分两步: > 1. 把数组变成一个大顶堆(**建堆**)。 > 2. 每次把堆顶(最大值)和数组末尾交换,然后对剩下的部分重新调整成大顶堆(**下沉**),直到堆空。 > 💬 **Q:如果数组数量是 n,那就是要建 n 次堆吗?** > > **不是**,这是一个常见的认知误区。实际上是 **建 1 次堆 + n-1 次下沉调整**,两者代价天差地别。 > > **建堆(只做 1 次)** > > 对完全无序的数组,从最后一个非叶子节点倒着下沉到根。这个过程代价是 O(n)。 > > **下沉调整(做 n-1 次)** > > 每轮排序:交换堆顶和末尾 → 剩下的部分**只有堆顶这一个位置可能不满足堆性质**,其他地方都还是合法的堆。所以只需要从根节点下沉一次就能恢复,代价是 O(log n),**不是重新建堆**。 > > 为什么不用重新建堆?看看交换前后的差异: > > ``` > 排序前的堆(合法): > 16 > / \ > 14 10 > / \ / \ > 8 7 9 3 > > 交换堆顶 16 和末尾 3 后: > 3 ← 只有这里不对 > / \ > 14 10 > / \ / > 8 7 9 ← 16 已经被"拿走"了(固定到末尾) > > 左右子树 [14, 8, 7] 和 [10, 9] 本身仍然是合法的堆! > 所以只需要对根节点 3 执行一次下沉,整棵树就恢复合法了。 > ``` > > **代价对比**: > > | 做法 | 单次代价 | 总代价 | > |------|---------|--------| > | 每轮都重新建堆(错误) | O(n) | n × O(n) = **O(n²)** | > | 只下沉堆顶(正确) | O(log n) | n × O(log n) = **O(n log n)** | > > 如果真的每轮都重建堆,堆排序就退化成 O(n²) 了,和冒泡一个档次,没人用了。堆排序的精妙就在于**利用"子树仍然合法"的性质**,避免了不必要的重建。 类比:桌上放 10 张牌,你要升序排列: - 第一步:重新摆一下,让最大的牌露在顶上。 - 第二步:把最大的牌拿走放到最右边(它就不动了),对剩下 9 张牌重新调整让最大的露在顶上。 - 重复,直到桌上没牌。 ``` 建堆后:[16, 14, 10, 8, 7, 9, 3, 2, 4, 1] ↑ 第 1 轮:16 和 1 交换 → [1, 14, 10, 8, 7, 9, 3, 2, 4, | 16] 对前 9 个下沉 → [14, 8, 10, 4, 7, 9, 3, 2, 1, | 16] 第 2 轮:14 和 1 交换 → [1, 8, 10, 4, 7, 9, 3, 2, | 14, 16] 对前 8 个下沉 → [10, 8, 9, 4, 7, 1, 3, 2, | 14, 16] ... 最终:[1, 2, 3, 4, 7, 8, 9, 10, 14, 16] ``` ## 核心操作:下沉(siftDown / heapify) 下沉就一句话:**和较大的孩子比,如果比孩子小就交换,继续往下沉。** ``` 当前节点是 i,考虑它的左右孩子: 1. 找出 i, left, right 中最大的那个,设为 largest 2. 如果 largest == i,说明 i 已经比两个孩子都大,结束 3. 否则交换 i 和 largest,然后对 largest 继续递归下沉 ``` ### 手动模拟下沉 ``` 数组:[3, 14, 10, 8, 7, 9, 1, 2, 4, 16] 对下标 0(值 3)下沉,堆大小 10: i=0 (3),左孩子 14,右孩子 10 → largest = 1 (14) 交换 → [14, 3, 10, 8, 7, 9, 1, 2, 4, 16] 继续对 i=1 下沉 i=1 (3),左孩子 8,右孩子 7 → largest = 3 (8) 交换 → [14, 8, 10, 3, 7, 9, 1, 2, 4, 16] 继续对 i=3 下沉 i=3 (3),左孩子 2,右孩子 4 → largest = 8 (4) 交换 → [14, 8, 10, 4, 7, 9, 1, 2, 3, 16] 继续对 i=8 下沉 i=8 (3),没有孩子(2*8+1=17 超出范围),结束 ``` ## 建堆:从最后一个非叶子节点开始下沉 ``` 为什么从最后一个非叶子节点开始? 叶子节点本身就是一个合法的堆(只有它自己),不用调整。 最后一个非叶子节点的下标是 n/2 - 1。 从 n/2 - 1 倒着到 0,对每个节点下沉一次,就能把整个数组变成一个堆。 数组 [4, 1, 3, 2, 16, 9, 10, 14, 8, 7],n = 10 最后一个非叶子节点下标:10/2 - 1 = 4 倒着下沉: i=4 (16):已经是叶子的父节点,孩子是 7,16 > 7,不动 i=3 (2):左孩子 14,右孩子 8 → 交换 2 和 14 → [4, 1, 3, 14, 16, 9, 10, 2, 8, 7] i=2 (3):左孩子 9,右孩子 10 → 交换 3 和 10 → [4, 1, 10, 14, 16, 9, 3, 2, 8, 7] i=1 (1):左孩子 16,右孩子 7 → 交换 1 和 16 → [4, 16, 10, 14, 1, 9, 3, 2, 8, 7] 继续对下标 4 下沉:左孩子 7,1 < 7 → 交换 → [4, 16, 10, 14, 7, 9, 3, 2, 8, 1] i=0 (4):左孩子 16,右孩子 10 → 交换 4 和 16 → [16, 4, 10, 14, 7, 9, 3, 2, 8, 1] 继续对下标 1 下沉:左孩子 14,右孩子 7 → 交换 4 和 14 → [16, 14, 10, 4, 7, 9, 3, 2, 8, 1] 继续对下标 3 下沉:左孩子 2,右孩子 8 → 交换 4 和 8 → [16, 14, 10, 8, 7, 9, 3, 2, 4, 1] 建堆完成:[16, 14, 10, 8, 7, 9, 3, 2, 4, 1] ``` ## 代码 ```java public int[] sortArray(int[] nums) { int n = nums.length; // 1. 建堆:从最后一个非叶子节点倒着下沉 for (int i = n / 2 - 1; i >= 0; i--) { siftDown(nums, i, n); } // 2. 排序:每次把堆顶和末尾交换,然后缩小堆的范围重新下沉 for (int i = n - 1; i > 0; i--) { swap(nums, 0, i); siftDown(nums, 0, i); } return nums; } private void siftDown(int[] nums, int i, int heapSize) { int l = i * 2 + 1, r = i * 2 + 2, largest = i; if (l < heapSize && nums[l] >nums[largest]) { largest = l; } if (r < heapSize && nums[r] > nums[largest]) { largest = r; } if (largest != i) { //i位置搞定了 swap(nums, i, largest); //但是由于i位置和largest位置变换了,需要下沉largest位置 siftDown(nums, largest, heapSize); } } private void swap(int[] nums, int a, int b) { int tmp = nums[a]; nums[a] = nums[b]; nums[b] = tmp; } ``` ## 复杂度分析 ``` 建堆:O(n) 看起来像 O(n log n),但数学上可以证明是 O(n)。 因为大部分节点都在靠近叶子的层,下沉的距离很短。 每次下沉:O(log n) 堆的高度是 log n。 排序:n 次下沉,O(n log n) 总时间复杂度:O(n log n) 空间复杂度:O(1)(原地排序,只有交换用的常数空间) ``` ### 为什么建堆是 O(n) 而不是 O(n log n)? ``` 第 h 层的节点数:约 n / 2^(h+1) 第 h 层节点下沉的最大距离:h 总代价 = Σ (n / 2^(h+1)) × h = n × Σ h / 2^(h+1) = n × (常数) ← 这个级数收敛到一个常数 = O(n) ``` 直观理解:**靠近叶子的节点多但下沉距离短,靠近根的节点少但下沉距离长**,加权求和后是 O(n)。 ## 注意:为什么升序用大顶堆,降序用小顶堆? ``` 大顶堆:堆顶是最大值 每次把堆顶(最大值)换到末尾,末尾的位置就固定下来不再参与 → 最大值放最后,次大放倒数第二 ... 结果是升序 小顶堆:堆顶是最小值 每次把堆顶(最小值)换到末尾 → 最小值放最后 ... 结果是降序 ``` 很多人第一次会搞反,记住一个口诀:**换到末尾谁就留在那里**。 ## 下沉 vs 上浮 ``` 下沉(siftDown):元素大了往下走。用在"堆顶被替换后重新调整"。 上浮(siftUp): 元素大了往上走。用在"向堆中插入新元素"。 堆排序只需要下沉,因为始终是对已有的堆进行调整,不涉及插入。 ``` ### 两种建堆方式 ``` 方式 1:从最后一个非叶子节点开始下沉(推荐) for (int i = n/2 - 1; i >= 0; i--) siftDown(i) 时间复杂度:O(n) 方式 2:从第一个节点开始上浮 for (int i = 1; i < n; i++) siftUp(i) 时间复杂度:O(n log n) ``` 方式 1 更快,原因如前所述。 ## 注意:容易踩的坑 ``` Q:堆排序是稳定排序吗? A:不是。下沉过程中会交换不相邻的元素,相等元素的相对顺序会被打乱。 Q:堆和优先队列(PriorityQueue)是一回事吗? A:优先队列是一种抽象数据结构,底层常用堆实现。 Java 的 PriorityQueue 默认是小顶堆。 Q:堆排序和快排哪个快? A:理论上都是 O(n log n),但实际堆排序常数更大(缓存不友好,跳跃访问数组), 工程上快排通常更快。但堆排序最坏情况稳定在 O(n log n),没有快排退化的风险。 Q:如果只要前 K 大的元素,要不要排完整个数组? A:不用。维护一个大小为 K 的小顶堆: 遍历数组,堆未满就加入;堆满了就比堆顶,比堆顶大就替换堆顶再下沉。 最后堆里剩的就是前 K 大,时间 O(n log k)。这就是 Top-K 经典解法。 ``` ## 应用:Top-K 问题(LeetCode 215) ```java public int findKthLargest(int[] nums, int k) { // 维护大小为 k 的小顶堆,堆顶就是第 k 大 PriorityQueue<Integer> heap = new PriorityQueue<>(); for (int num : nums) { heap.offer(num); if (heap.size() > k) heap.poll(); } return heap.peek(); } ``` 时间 O(n log k),比完整排序快。 ## 应用:合并 K 个有序链表(LeetCode 23) 把每个链表的头节点放进小顶堆,每次取堆顶接到结果链表,然后把这个节点的 next 放回堆中。时间 O(N log K),其中 N 是所有节点总数,K 是链表数。 ## 一句话总结 堆排序 = 建堆 + n 次"交换堆顶到末尾 + 下沉"。核心操作是下沉(和较大孩子比,小就换)。建堆 O(n),排序 O(n log n),原地排序但不稳定。 --- 上一篇:[01 - 快速排序](./01-quick-sort.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入