元数据卡

• 前置知识：二叉树（第5章）、数组（第2章）
• 核心难度：进阶
• 完成标志：能实现上浮/下沉操作，理解 Floyd 建堆 O(n) 的直觉

---

你的背包里有一堆任务卷轴，每个标着优先级。你只关心哪张最紧急——不想每次翻遍整个背包找它。排序？插入一次 O(n) 重建。哈希表？它不懂"大小比较"。BST 能做，但它的全序能力远超你的需求，而且每个节点三个指针加颜色标记，太重了。

你需要一个偏科的结构：不在乎谁第二，只在乎谁第一。这就是堆。

---

破局：堆是什么

堆是一个完全二叉树——除最后一层可能不满，上面全满，最后一层靠左填充。这个形状保证了用数组存它时没有空洞：

索引:    0   1   2   3   4   5   6
数组:  [10,  7,  8,  5,  3,  6,  4]

树形:
         10
        /  \
       7    8
      / \  / \
     5  3 6   4

父子关系的索引规则：左子 2*i+1，右子 2*i+2，父节点 (i-1)/2。不需要指针。

完全二叉树的约束再加一条就是堆：最大堆：父 >= 子，堆顶是最大值；最小堆：父 <= 子，堆顶是最小值。兄弟节点之间没有顺序约定——堆只保证"半有序"。

---

动手：Java 最大堆实现

// MaxHeap.java — 最大堆（完整实现）
// 编译：javac MaxHeap.java
// 运行：java MaxHeap

import java.util.ArrayList;
import java.util.List;

public class MaxHeap {
    private List<Integer> heap = new ArrayList<>();

    public void push(int val) {
        heap.add(val);                           // 扔到末尾
        int i = heap.size() - 1;
        while (i > 0) {                         // 上浮：和父比，大就换
            int p = (i - 1) / 2;
            if (heap.get(p) >= heap.get(i)) break;
            int tmp = heap.get(p);
            heap.set(p, heap.get(i));
            heap.set(i, tmp);
            i = p;
        }
    }

    public int pop() {
        if (heap.isEmpty()) throw new RuntimeException("空堆");
        if (heap.size() == 1) return heap.remove(0);
        int max = heap.get(0);
        heap.set(0, heap.remove(heap.size() - 1)); // 末尾顶到堆顶
        int i = 0, n = heap.size();
        while (true) {                           // 下浮：两子中选大的换
            int largest = i, left = 2 * i + 1, right = 2 * i + 2;
            if (left < n && heap.get(left) > heap.get(largest)) largest = left;
            if (right < n && heap.get(right) > heap.get(largest)) largest = right;
            if (largest == i) break;
            int tmp = heap.get(i);
            heap.set(i, heap.get(largest));
            heap.set(largest, tmp);
            i = largest;
        }
        return max;
    }

    public static void main(String[] args) {
        MaxHeap h = new MaxHeap();
        for (int v : new int[]{5, 3, 8, 1, 7}) h.push(v);
        System.out.println("堆: " + h.heap);               // [8, 7, 5, 1, 3]
        System.out.println("pop: " + h.pop() + " " + h.pop()); // 8 7
        System.out.println("剩余: " + h.heap);              // 最大堆形态之一
    }
}

预期输出：

堆: [8, 7, 5, 1, 3]
pop: 8 7
剩余: [5, 3, 1]

上浮（push）像气泡向上冒，下浮（pop）像空降到顶往下沉。复杂度都是 O(log n)——树高 log₂n，每次最多走一条根到叶的路径。

---

深入：Floyd 建堆 O(n)

给你无序数组 [3, 1, 6, 5, 2, 4]，怎么建堆？最直觉是一个个 push —— O(n log n)，建个堆而已不至于。

Floyd：从最后一个非叶节点 (n/2 - 1) 倒着往下浮。叶子不用管（单节点已是合法堆），每往上一层，下浮时子树已处理好了。

// FloydBuildHeap.java — O(n) 建堆
// 编译：javac FloydBuildHeap.java
// 运行：java FloydBuildHeap

public class FloydBuildHeap {
    public static void buildMaxHeap(int[] arr) {
        for (int i = arr.length / 2 - 1; i >= 0; i--)
            siftDown(arr, i, arr.length);
    }

    private static void siftDown(int[] arr, int i, int n) {
        while (true) {
            int largest = i, left = 2 * i + 1, right = 2 * i + 2;
            if (left < n && arr[left] > arr[largest]) largest = left;
            if (right < n && arr[right] > arr[largest]) largest = right;
            if (largest == i) break;
            int t = arr[i]; arr[i] = arr[largest]; arr[largest] = t;
            i = largest;
        }
    }

    public static void main(String[] args) {
        int[] arr = {3, 1, 6, 5, 2, 4};
        buildMaxHeap(arr);
        for (int v : arr) System.out.print(v + " ");
        System.out.println();  // 6 5 4 1 2 3 （最大堆形态之一）
    }
}

为什么是 O(n) 不是 O(n log n)？大多数节点在底层：倒数第二层 n/4 个各下浮最多 1 次，倒数第三层 n/8 个各最多 2 次……总工作量 = 1 x n/4 + 2 x n/8 + 3 x n/16 + ... = n x 1 = O(n)。直觉：底层人多但几乎不动，顶层人少但动得多——但人太少，总工作量刷不起来。

---

常见陷阱

堆 vs BST。 堆只给堆顶最值，兄弟间无关系。BST 给全序，可查前驱后继。查任意元素用 BST，只关心最值用堆。

最大堆 vs 最小堆的方向。 Java PriorityQueue 默认最小堆。最大堆传 Comparator.reverseOrder()。TopK 用最小堆——反直觉但正确。

堆排序不稳定。 相等元素在下浮中可能交换相对顺序。

---

旅人笔记

堆是偏科的数据结构：不做随机访问，不做全排序，只快速给你最值。上浮 = 新人往上爬，下浮 = 空降往下沉，Floyd = 从底到顶稳扎稳打。

下一步：优先队列

Java 把堆封装成了 PriorityQueue，让你直接专注应用。

看优先队列 →