排序与堆¶

一句话：需要"全部有序"就用排序；只需要"前 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 个候选里最小的一个，新元素只有比它大才有资格顶替它）——直觉上想用大顶堆，但大顶堆的堆顶是"已扫描元素里最大的一个"，无法用来判断"要不要淘汰某个候选"。先想清楚"堆顶该扮演什么角色（候选集合里最弱的那个，用来判断谁该被淘汰）"，再决定大顶堆还是小顶堆。

手写堆：完全二叉树用数组装¶

为什么是数组，不是节点¶

堆是一棵完全二叉树（除最后一层外每层都满，最后一层节点靠左连续）。这个"完全"性质意味着层序编号 0..n-1 连续无空洞，所以父子关系可以直接算，不需要存指针：

下标 i 的父     = (i - 1) / 2
下标 i 的左孩子 = 2 * i + 1
下标 i 的右孩子 = 2 * i + 2

数组:  [1, 3, 2, 5, 9, 8, 7]
下标:   0  1  2  3  4  5  6

树（层序填）:
              1(0)
            /      \
         3(1)      2(2)
        /    \     /   \
      5(3)  9(4) 8(5)  7(6)

数组是树在内存里的紧凑投影。换成链式节点（left/right 引用）代价明显：

	数组	链式节点
每元素开销	4 字节（int）	对象头 16B + 数据 + 2 个引用 ≈ 40B
父子定位	`(i-1)/2`、`2i+1` 算出来	逐层跳指针
CPU 缓存	连续内存，一个 cache line 覆盖多个节点	节点分散，频繁 cache miss
适用	完全二叉树（无空洞）	任意形状二叉树

反例：非完全二叉树用数组会大量留空——深度 10 的链状树只有 10 个节点，数组却要 2^10 = 1024 槽。"完全"这两个字就是为数组索引公式而存在的。

push / pop 与 siftUp / siftDown¶

堆只保证父 ≤ 子（小顶堆），兄弟之间无序——所以数组内容看起来是乱的，但根永远最小。

操作	动作	为什么
`push`	放数组末尾，再 `siftUp` 往上爬	末尾是"下一层最左边"的位置，保持完全二叉树形状
`pop`	取走 `heap[0]`，把末尾元素提到堆顶，再 `siftDown` 往下沉	直接删 `heap[0]` 会在数组开头留空洞破坏形状；末尾顶替后形状始终完整

siftUp（上浮）：和一个父比较，比父小就交换，往上爬；父 ≤ 自己或到根就停。

插入 3 到 [2,5,8]：
放末尾 [2,5,8,3] → 父 heap[1]=5 > 3 → 换 → [2,3,8,5]
                 → 父 heap[0]=2 ≤ 3 → 停

siftDown（下沉）：和两个孩子比较，比孩子大就交换——必须和「较小的那个孩子」交换。

为什么必须选较小的孩子：交换的目的是把更小的值顶上去当父。若和较大孩子（8）交换，留下的较小孩子（5）就会比新父（8）小，堆性质立刻崩掉。

poll [2,5,8,9,6]：
取 2 → 末尾 6 提到顶 [6,5,8,9]
→ 孩子 5、8，较小是 5，6 > 5 → 换 → [5,6,8,9]
→ i=1 孩子 9，6 ≤ 9 → 停

	siftUp	siftDown
用在	`push`	`pop`
方向	往上爬	往下沉
和谁比	1 个父节点	2 个孩子中较小的
交换条件	比父小	比孩子大
停止	父 ≤ 自己 / 到根	自己 ≤ 两个孩子 / 无孩子
复杂度	O(log heapSize) = 树高	同左

口诀：push 从底往上顶（新来的可能太小），pop 从顶往下沉（顶替者可能太大）。

两个版本：最小版 / 完整版¶

先明确"完整"指什么——手写堆不必一步到位，两种版本各自够用：

	最小版	完整版
构造	容量 `MinHeap(capacity)`	容量 + 数组 heapify
`siftUp`/`siftDown`	无参（push 固定末尾、pop 固定根）	带参（heapify/update/remove 需要任意起点）
扩容	❌ 容量给足，否则越界	✅ `ensureCapacity` 翻倍
改值修复	❌	✅ `update(i, v)`
删任意位置	❌	✅ `removeAt(i)`
适用	刷题手写 Top-K（347）	面试"手写优先队列"、需要动态增删的场景

最小版（347 够用）¶

/** 只服务 Top-K：容量由调用方给足，不扩容。 */
class MinHeapLite {
    private final int[] heap;
    private int size;

    MinHeapLite(int capacity) { heap = new int[capacity]; }

    int size()        { return size; }
    boolean isEmpty() { return size == 0; }
    int peek()        { return heap[0]; }

    void push(int v) {
        heap[size] = v;
        siftUp();          // 无参：新元素总在 size
        size++;
    }

    int pop() {
        int top = heap[0];
        size--;
        heap[0] = heap[size];
        siftDown();        // 无参：总从 0 开始
        return top;
    }

    private void siftUp() {
        int i = size;
        while (i > 0) {
            int p = (i - 1) / 2;
            if (heap[p] <= heap[i]) break;
            swap(p, i);
            i = p;
        }
    }

    private void siftDown() {
        int i = 0;
        while (true) {
            int l = 2 * i + 1, r = l + 1, min = i;
            if (l < size && heap[l] < heap[min]) min = l;
            if (r < size && heap[r] < heap[min]) min = r;
            if (min == i) break;
            swap(i, min);
            i = min;
        }
    }

    private void swap(int i, int j) { int t = heap[i]; heap[i] = heap[j]; heap[j] = t; }
}

唯一约束：capacity 必须给够。347 里传 k + 1（push 后可能暂时有 k+1 个，再 pop 淘汰一个），就刚好不越界。

完整版（对标 PriorityQueue）¶

class MinHeapFull {
    private int[] heap;      // 非 final：扩容要换引用
    private int size;

    /** ① 空堆：逐次 push */
    MinHeapFull(int capacity) { heap = new int[Math.max(1, capacity)]; }

    /** ② heapify 建堆 O(n)：从最后一个非叶子节点往前逐个下沉 */
    MinHeapFull(int[] data) {
        heap = data.clone();
        size = data.length;                              // 必须先设 size
        for (int i = size / 2 - 1; i >= 0; i--) siftDown(i);
    }

    int size()        { return size; }
    boolean isEmpty() { return size == 0; }
    int peek()        { return heap[0]; }

    void push(int v) {
        ensureCapacity();
        heap[size] = v;
        siftUp(size);
        size++;
    }

    int pop() {
        int top = heap[0];
        size--;
        heap[0] = heap[size];
        siftDown(0);
        return top;
    }

    /** 改下标 i 的值并恢复堆性质 */
    void update(int i, int newValue) {
        int old = heap[i];
        heap[i] = newValue;
        if (newValue < old) siftUp(i);        // 变小 → 只需上浮
        else if (newValue > old) siftDown(i); // 变大 → 只需下沉
    }

    /** 删除下标 i 的元素并返回它 */
    int removeAt(int i) {
        int removed = heap[i];
        size--;
        if (i == size) return removed;        // 删的就是末尾，无需修复
        heap[i] = heap[size];                 // 末尾顶替
        if (i > 0 && heap[i] < heap[(i - 1) / 2]) siftUp(i);  // 比父小 → 上浮
        else siftDown(i);                                     // 否则下沉
        return removed;
    }

    private void ensureCapacity() {
        if (size == heap.length) heap = Arrays.copyOf(heap, heap.length * 2);
    }

    private void siftUp(int i) {
        while (i > 0) {
            int p = (i - 1) / 2;
            if (heap[p] <= heap[i]) break;
            swap(p, i);
            i = p;
        }
    }

    private void siftDown(int i) {
        while (true) {
            int l = 2 * i + 1, r = l + 1, min = i;
            if (l < size && heap[l] < heap[min]) min = l;
            if (r < size && heap[r] < heap[min]) min = r;
            if (min == i) break;
            swap(i, min);
            i = min;
        }
    }

    private void swap(int i, int j) { int t = heap[i]; heap[i] = heap[j]; heap[j] = t; }
}

完整版的四个关键点： 1. heap 不能是 final —— 扩容要换引用 2. heapify 里 size = data.length 必须在循环前，因为 siftDown 靠 size 判断孩子是否存在 3. heapify 起点 size/2 - 1 是最后一个非叶子节点；更大的下标都是叶子，天然是合法堆。整体 O(n)（不是 O(n log n)） 4. removeAt 只修复一个方向：末尾顶替后，若比父小就上浮，否则下沉——两种情况互斥

最大堆只需把比较符号反过来：heap[p] >= heap[i]、heap[l] > heap[max]、heap[r] > heap[max]。

Java 实战默认用 PriorityQueue（内部就是这套二叉堆 + 数组 + 扩容）：默认小顶堆，offer/poll/peek 对应 push/pop/peek。只有面试官明说"不许用 PriorityQueue"才手写；手写时至少要补上扩容，容量写死是真实缺陷。

变体：二元组压进一个 int（纯 int 堆 + 编码）¶

347 前 K 个高频元素 要按频率排序，但堆里想存 (值, 频率) 二元组——除了二维数组 / 传 map 进堆 / 比较器，还可以把二元组编码成一个 int，让标准 int 堆直接工作：

// 编码：频率放高位，值放低位（本题 值 ∈ [-1000,1000]，+1000 消负数）
int code = 频率 * 10000 + (值 + 1000);
heap.push(code);
// 解码
int 值 = code % 10000 - 1000;

比较 code 就等于"先比频率、再比值"，正是需要的顺序。前提是值域有限：要求 最大频率 × 值域宽度 < 2^31（本题 10^5 × 10^4 = 10^9，安全）。值域是 int 全域时必须改用 long 编码或比较器方案。

堆和 map 的职责分离：HashMap 只负责计数，堆只负责选择；堆是"排序/选择器"，不是"数据仓库"——数据留在 map 里，需要权重时按身份去查。（用 PriorityQueue<Integer> + (a,b) -> freq.get(a) - freq.get(b) 就是这个形态。）

易错点¶

swap 三步写反会变成"复制"：heap[j] = heap[i] 会把 heap[j] 的原值覆盖掉，结果两个位置都等于原 heap[i]。症状：结果里出现重复值（如 [1,1,1,2,2,3] k=2 输出 [1,1]）。正确：int t = heap[i]; heap[i] = heap[j]; heap[j] = t;
求前 K「大」用小顶堆（堆顶是这 K 个里最小的，用来判断谁该被淘汰）；求前 K「小」用大顶堆。方向反了逻辑就崩
siftDown 必须和较小的孩子交换，否则堆性质被破坏
pop 用末尾元素顶替堆顶，不要直接删 heap[0]——形状会破
出堆顺序是小顶堆的升序（即堆排序），题目要求逆序时注意是否需要额外翻转
容量写死是真实缺陷：MinHeap(capacity) 不扩容时，push 到第 capacity+1 个就 ArrayIndexOutOfBounds。347 侥幸没炸是因为传了 k+1 且元素数不会更多；通用实现必须 ensureCapacity 翻倍扩容（此时 heap 字段不能是 final）
heapify 里 size 必须先赋值再进 siftDown 循环，否则 siftDown 判断"孩子是否存在"时用的是旧的 size=0
removeAt(i) 删除末尾时直接返回，不要走"末尾顶替 + 修复"，否则会把同一个元素又放回去