排序与堆

一句话：需要”全部有序”就用排序；只需要”前 K 个”或”动态维护当前最值”，用堆——堆的本质是一棵只保证”父节点比子节点更优”、不要求兄弟节点之间有序的弱化二叉树，正是这个弱化换来了 O(log n) 的插入/取出，比维护整体有序便宜得多。

排序：先想清楚要不要真的排全序

912-排序数组 是各种排序算法的练习场（快排的分区、归并的合并、堆排序），但更重要的教训在别处：56-合并区间、252/253-会议室 都不是”排序题”，而是先按某一维排序，把问题转化为一次线性扫描——56 按区间左端点排序后，重叠的区间必然相邻，一次遍历即可合并；253 按开始时间排序后，用一个小顶堆维护”当前正在使用、最早结束”的会议室，新会议开始时间 ≥ 堆顶结束时间就复用，否则新开一间。排序在这里只是预处理，真正的解法是排序之后的那一次扫描或者堆的运用。

75-颜色分类 是”不需要真正排序”的反例：只有三种取值，用双指针一次遍历原地分区即可，O(n) 而不是通用排序的 O(n log n)——取值范围有限时，专用的线性算法总是优于通用排序，这也是计数排序/桶排序的适用场景。

堆：Top-K 问题不需要排序

215-数组中的第K个最大元素、347-前K个高频元素、703-数据流中的第K大 的共性是只关心第 K 名或前 K 名，不关心其余元素的相对顺序——这正是堆比排序便宜的地方：维护一个大小为 K 的小顶堆，堆顶就是”当前已扫描元素里的第 K 大”，新元素只有比堆顶大才有资格入堆（顶替堆顶），复杂度是 O(n log K) 而不是排序的 O(n log n)，当 K 远小于 n 时优势明显。

295-数据流的中位数 是堆的进阶应用：一个大顶堆存较小的一半，一个小顶堆存较大的一半，两堆大小差不超过 1，中位数就是堆顶（或两堆顶的平均）——这是”用两个堆把中间那个位置固定在堆顶”的技巧，本质仍是”不需要整体有序，只需要能 O(log n) 维护某个特定位置的值”。

23-合并K个排序链表 用小顶堆维护”K个链表当前各自最小的头节点”，每次弹出全局最小值、放入其所在链表的下一个节点——把”K路归并”从”每次线性扫描K个候选找最小”（O(K)）降到了”堆弹出/插入”（O(log K)）。

易错点：堆维护的是”候选集合”不是”最终答案”

用堆做 Top-K 时最容易搞反的方向：要找最大的 K 个，反而要维护一个小顶堆（堆顶是这 K 个候选里最小的一个，新元素只有比它大才有资格顶替它）——直觉上想用大顶堆，但大顶堆的堆顶是”已扫描元素里最大的一个”，无法用来判断”要不要淘汰某个候选”。先想清楚”堆顶该扮演什么角色（候选集合里最弱的那个，用来判断谁该被淘汰）“，再决定大顶堆还是小顶堆。