罗罗编程学习记录
本页内容 展开查看

02.4.1.4 堆与 Trie 树

所属:全栈开发面试题库 / 02 数据结构与算法 / 02.4 树与图 / 02.4.1 二叉树与遍历

02.4.1.4-001 堆在树形结构中处于什么位置?

一句话结论

堆是满足堆序的完全二叉树,通常数组存储;与 BST 不同,堆只保证父子大小关系,兄弟无序;用于优先队列与 Top-K,详细操作见 02.3.2.4。

概念解释

  • 堆序:父 ≥ 子(大顶)或父 ≤ 子(小顶)。
  • 完全二叉树。
  • 不全局有序。

原理流程

  1. 数组按层序存树。
  2. 插入上浮、删除下沉维护堆序。
  3. 堆顶为最值。

代码 / 图示

大顶堆:根最大,兄弟无序

常见误区

  • 误区:堆是排序树;正解:只维护堆顶最值。
  • 误区:堆必须链表存储;正解:完全树用数组最紧凑。

追问

  • Q:堆与 BST 区别? A:堆父子有序、兄弟无序;BST 中序有序。
  • Q:堆支持查找任意值? A:不支持高效查找。

02.4.1.4-002 堆的数组下标怎么映射?

一句话结论

下标 0 起:父 (i-1)/2,左孩子 2i+1,右孩子 2i+2;完全二叉树无空洞,数组紧凑存储;孩子越界需判断。

概念解释

  • 层序编号。
  • 父子公式。
  • 边界判断。

原理流程

  1. 根下标 0。
  2. 按层序填数组。
  3. 公式定位父子。

代码 / 图示

父:(i-1)/2
左:2i+1  右:2i+2

常见误区

  • 误区:0 起与 1 起公式混用;正解:统一口径。
  • 误区:孩子下标越界不判;正解:下沉前检查孩子存在。

追问

  • Q:1 起公式? A:父 i/2,左 2i,右 2i+1。
  • Q:叶子判断? A:左孩子下标 ≥ 长度。

02.4.1.4-003 堆插入与上浮怎么做?

一句话结论

新元素放末尾,与父比较违反堆序则交换并继续上浮;O(log n);大顶堆上浮到父更大为止。

概念解释

  • 末尾插入。
  • 上浮维护堆序。
  • 沿父链上移。

原理流程

  1. 追加末尾。
  2. 与父比较。
  3. 违反则交换上移。

代码 / 示例

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

常见误区

  • 误区:插入后全局排序;正解:只上浮到满足父子关系。
  • 误区:相等仍交换;正解:相等不违反堆序,可停。

追问

  • Q:上浮交换次数? A:树高 O(log n)。
  • Q:小顶堆方向? A:父更小,上浮条件反向。

02.4.1.4-004 删除堆顶与下沉怎么做?

一句话结论

末尾元素覆盖堆顶,规模减一;与合适孩子比较,违反堆序则交换下沉;O(log n);大顶堆选较大孩子交换。

概念解释

  • 堆顶移除。
  • 末尾补位。
  • 下沉恢复堆序。

原理流程

  1. 堆顶 = 末尾。
  2. 规模减一。
  3. 选孩子比较交换下沉。

代码 / 示例

int pop() {
    int top = heap[0];
    heap[0] = heap[--size];
    int i = 0;
    while (true) {
        int l = 2 * i + 1, r = l + 1, best = i;
        if (l < size && heap[l] > heap[best]) best = l;
        if (r < size && heap[r] > heap[best]) best = r;
        if (best == i) break;
        swap(i, best); i = best;
    }
    return top;
}

常见误区

  • 误区:下沉不比较孩子大小;正解:大顶堆选较大孩子。
  • 误区:末尾元素直接丢弃;正解:补到堆顶再下沉。

追问

  • Q:堆空 pop? A:先判空。
  • Q:下沉到叶子? A:无孩子可交换即停。

02.4.1.4-005 建堆复杂度为什么是 O(n)?

一句话结论

自底向上从最后非叶子节点逐个下沉,低层节点多但下沉距离短,按层求和收敛为 O(n);逐个插入建堆才是 O(n log n)。

概念解释

  • 自底向上。
  • 层代价求和。
  • 线性收敛。

原理流程

  1. 从最后非叶子向前。
  2. 逐个下沉。
  3. 各层步数求和。

代码 / 图示

Σ 2^k · (h-k) = O(n)

常见误区

  • 误区:建堆 O(n log n);正解:原地自底向上 O(n)。
  • 误区:插入法建堆也是 O(n);正解:插入法 O(n log n)。

追问

  • Q:堆排序总复杂度? A:建堆 O(n) + 反复取顶 O(n log n)。
  • Q:面试怎么证明? A:按层节点数乘下沉距离求和。

02.4.1.4-006 堆排序思路是什么?

一句话结论

建大顶堆后反复把堆顶换末尾,规模减一再下沉;升序输出;O(n log n) 时间 O(1) 额外空间,不稳定。

概念解释

  • 堆顶最大值。
  • 交换到末尾固定。
  • 剩余堆下沉恢复。

原理流程

  1. 原地建大顶堆。
  2. 堆顶换末尾。
  3. 规模减一,下沉堆顶。

代码 / 图示

大顶堆 → 最大值在根 → 换末尾 → 剩余下沉

常见误区

  • 误区:堆排序稳定;正解:跨距交换不稳定。
  • 误区:建堆 O(n log n);正解:建堆 O(n),排序阶段 O(n log n)。

追问

  • Q:为什么工程少用堆排? A:缓存局部性不如快排,不稳定。
  • Q:小顶堆排升序? A:方向相反,按实现口径。

02.4.1.4-007 Top-K 用堆怎么选堆方向?

一句话结论

前 K 大用大小 K 的小顶堆,堆顶为当前 K 个中最小,便于淘汰;前 K 小用大顶堆;O(n log K) 时间 O(K) 空间。

概念解释

  • 堆规模 K。
  • 堆顶为淘汰边界。
  • 超界替换。

原理流程

  1. 先放 K 个入堆。
  2. 后续与堆顶比较。
  3. 更优则替换下沉。

代码 / 示例

Queue<Integer> heap = new PriorityQueue<>(); // 小顶堆,前 K 大
for (int x : nums) {
    heap.offer(x);
    if (heap.size() > k) heap.poll();
}

常见误区

  • 误区:前 K 大用大顶堆;正解:小顶堆淘汰最小。
  • 误区:堆规模 n;正解:固定 K。

追问

  • Q:K 接近 n? A:log K 接近 log n,可直接排序。
  • Q:流式 Top-K? A:堆只留 K,O(K) 空间。

02.4.1.4-008 Trie(前缀树)是什么结构?

一句话结论

Trie 是按字符串前缀共享路径的多叉树:边代表字符,节点代表前缀;根为空串,节点可标记单词结束;支持插入、查询、前缀匹配。

概念解释

  • 路径:字符序列。
  • 共享:公共前缀合并。
  • 结束标记:区分前缀与完整单词。

原理流程

  1. 根出发按字符走边。
  2. 缺边则新建节点。
  3. 单词末尾打标记。

代码 / 图示

根 → c → a → t(结束)
            → b(结束)

常见误区

  • 误区:Trie 节点存完整字符串;正解:节点存字符/子节点映射,路径拼词。
  • 误区:无结束标记也能判断完整单词;正解:前缀不等于单词。

追问

  • Q:Trie 适用字符集? A:小写字母用数组,大字符集用哈希映射。
  • Q:与哈希表比前缀能力? A:Trie 天然支持前缀遍历。

02.4.1.4-009 Trie 插入怎么做?

一句话结论

从根按单词字符逐位查找,缺子节点则新建;走到末尾标记单词结束;O(L) 时间,L 为单词长度。

概念解释

  • 逐字符走边。
  • 缺边新建。
  • 结束标记。

原理流程

  1. 指针从根开始。
  2. 每字符查子节点,缺则建。
  3. 末尾置 end。

代码 / 示例

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean end = false;
}
public void insert(String word) {
    TrieNode cur = root;
    for (char c : word.toCharArray()) {
        int i = c - 'a';
        if (cur.children[i] == null) cur.children[i] = new TrieNode();
        cur = cur.children[i];
    }
    cur.end = true;
}

常见误区

  • 误区:插入重复单词重复建路径;正解:已有路径复用,只置标记。
  • 误区:结束标记遗漏;正解:前缀词与完整词需区分。

追问

  • Q:多位数组大小? A:按字符集,26 小写字母。
  • Q:大小写敏感? A:按题目约定统一处理。

02.4.1.4-010 Trie 查询完整单词怎么做?

一句话结论

按字符走边,中途缺边返回 false;走完后必须节点 end 为 true,才是完整单词;仅路径存在只说明是前缀。

概念解释

  • 路径存在 ≠ 单词结束。
  • 结束标记判定。
  • 中途失败。

原理流程

  1. 逐字符查子节点。
  2. 缺边返回 false。
  3. 末尾检查 end。

代码 / 示例

public boolean search(String word) {
    TrieNode cur = root;
    for (char c : word.toCharArray()) {
        TrieNode next = cur.children[c - 'a'];
        if (next == null) return false;
        cur = next;
    }
    return cur.end;
}

常见误区

  • 误区:走到节点即存在单词;正解:必须 end 为 true。
  • 误区:缺边继续查空;正解:立即返回 false。

追问

  • Q:查询前缀是否存在? A:不检查 end,走到即存在。
  • Q:通配符查询? A:点号遍历所有子节点递归。

02.4.1.4-011 Trie 前缀匹配怎么做?

一句话结论

走到前缀对应节点,该子树所有单词即以该前缀开头;DFS/BFS 收集子树路径;前缀存在性查询 O(L)。

概念解释

  • 前缀节点:子树根。
  • 子树遍历收集。
  • 共享前缀复用。

原理流程

  1. 走到前缀节点。
  2. 遍历子树拼路径。
  3. 收集 end 节点单词。

代码 / 图示

前缀 "ca" 子树 → cat, cab, cap ...

常见误区

  • 误区:前缀匹配只查单节点;正解:需遍历子树枚举单词。
  • 误区:收集非 end 路径;正解:只收完整单词。

追问

  • Q:自动补全用什么? A:Trie 子树遍历 + 热度排序。
  • Q:前缀计数? A:节点维护经过次数。

02.4.1.4-012 Trie 删除怎么做?

一句话结论

先确认单词存在,再逆序删除无子节点且非结束标记的节点;被删单词若为其他词前缀,只清除 end 标记不删路径;O(L) 时间。

概念解释

  • 逆序清理。
  • 共享路径保留。
  • 标记与节点区分。

原理流程

  1. 查找路径记录节点。
  2. 清除末尾 end。
  3. 逆序删空叶子,有共享则停。

代码 / 图示

cat 存在,car 共享 ca 路径
删 cat:删 t,保留 c-a

常见误区

  • 误区:删除整条路径影响共享词;正解:有子节点或 end 则保留。
  • 误区:单词不存在也删;正解:先校验存在性。

追问

  • Q:迭代删除? A:栈记录路径逆序处理。
  • Q:Trie 适合频繁删除吗? A:可做,空间回收需判断共享。

02.4.1.4-013 Trie 节点怎么维护词频与前缀计数?

一句话结论

节点维护 count(经过该前缀的单词数)与 endCount(以该节点结束的单词数);插入时沿途累加,删除时递减;可统计前缀出现次数。

概念解释

  • 前缀计数:沿途经过次数。
  • 词频:结束节点计数。
  • 增量维护。

原理流程

  1. 插入沿途 count++,末尾 endCount++。
  2. 查询直接读计数。
  3. 删除对应递减。

代码 / 图示

node.pass:经过前缀次数
node.end:结束单词数

常见误区

  • 误区:只记结束计数无法求前缀频次;正解:沿途 pass 计数。
  • 误区:重复插入未累加;正解:重复词频递增。

追问

  • Q:前 K 热词? A:计数 + 堆遍历子树。
  • Q:删除计数归零处理? A:标记空闲可回收。

02.4.1.4-014 Trie 与哈希表怎么对比?

一句话结论

哈希表按键整体哈希 O(L) 插入查询,不支持前缀;Trie 按字符共享前缀,支持前缀匹配、自动补全与字典序遍历;前缀密集场景 Trie 更省重复存储。

概念解释

  • 哈希:整键散列。
  • Trie:路径共享。
  • 前缀能力差异。

原理流程

  1. 看是否需要前缀查询。
  2. 看字符集与重复度。
  3. 选型。

代码 / 图示

精确取值:哈希 O(L)
前缀/补全:Trie

常见误区

  • 误区:Trie 查询 O(1);正解:O(L),L 为串长。
  • 误区:Trie 空间恒优于哈希;正解:稀疏字符集下节点开销大。

追问

  • Q:大字符集 Trie 怎么省空间? A:压缩 Trie/哈希映射子节点。
  • Q:字典序遍历? A:Trie 子节点按序遍历。

02.4.1.4-015 Trie 空间复杂度怎么算?

一句话结论

最坏 O(字符集 × 总字符数),共享前缀后实际节点数等于所有单词不同前缀路径数;数组子节点按字符集定宽,哈希映射按需建子节点。

概念解释

  • 节点数:不同前缀。
  • 每节点子节点开销。
  • 共享降低节点数。

原理流程

  1. 统计插入后不同前缀。
  2. 单节点子节点结构开销。
  3. 合计空间。

代码 / 图示

无共享:Σ 单词长度
有共享:不同前缀路径数

常见误区

  • 误区:Trie 空间 O(单词数);正解:按字符路径计。
  • 误区:26 数组无空开销;正解:空引用也占节点内数组空间。

追问

  • Q:压缩前缀树? A:单链路径合并成边,省节点。
  • Q:超长公共前缀收益? A:共享越多越省。

02.4.1.4-016 Trie 怎么支持通配符匹配?

一句话结论

查询遇通配符(如 .)遍历当前节点所有子节点递归匹配;普通字符走对应子节点;O(字符集^匹配位置) 最坏,通常剪枝。

概念解释

  • 通配:多分支。
  • 递归逐字符。
  • 结束标记判定。

原理流程

  1. 普通字符走唯一子边。
  2. 通配遍历全部子节点。
  3. 末尾检查 end。

代码 / 示例

boolean dfs(TrieNode node, String w, int i) {
    if (node == null) return false;
    if (i == w.length()) return node.end;
    char c = w.charAt(i);
    if (c == '.') {
        for (TrieNode next : node.children) if (dfs(next, w, i + 1)) return true;
        return false;
    }
    return dfs(node.children[c - 'a'], w, i + 1);
}

常见误区

  • 误区:通配只匹配一个字符口径混乱;正解:按题目通配语义。
  • 误区:空 children 遍历越界;正解:判空。

追问

  • Q:LC 211 添加与搜索单词? A:本框架递归实现。
  • Q:多通配符模式? A:结合正则或 DP。

02.4.1.4-017 Trie 怎么做最大异或对?

一句话结论

二进制位 Trie 按 0/1 分支插入每个数的二进制高位;查询时优先走相反位求最大异或;O(n·L),L 为位数;是位运算与 Trie 的结合考点。

概念解释

  • 位路径:高位到低位。
  • 贪心反位。
  • 异或最大值。

原理流程

  1. 数按位插入 0/1 树。
  2. 查询每位优先选反位。
  3. 拼出最大异或值。

代码 / 图示

高位优先:反位异或为 1

常见误区

  • 误区:按十进制字符建 Trie;正解:按二进制位分支。
  • 误区:低位优先;正解:高位对结果贡献最大。

追问

  • Q:位数固定多少? A:按数值范围定 30/31 位。
  • Q:离线排序替代? A:分治求异或对,Trie 更直接。

02.4.1.4-018 堆与 Trie 题有哪些边界用例?

一句话结论

空输入、单元素、全相同值、字符空串、单字符单词、前缀即完整单词、重复插入、字符集越界;判空、结束标记与计数口径。

概念解释

  • 空与最短。
  • 等值/重复。
  • 前缀与单词重叠。

原理流程

  1. 空结构返回默认。
  2. 单元素走边界分支。
  3. 标记与计数复核。

代码 / 图示

空堆 / 单元素
"" / "a" / 前缀词

常见误区

  • 误区:空串插入建根 end;正解:按题目约定。
  • 误区:堆空取顶;正解:先判空。

追问

  • Q:Trie 查空串? A:返回根 end 标记。
  • Q:堆全相同元素? A:堆序仍成立,顺序不保证。

02.4.1.4-019 堆与 Trie 复杂度怎么汇报?

一句话结论

堆插入/取顶 O(log n),建堆 O(n),Top-K O(n log K)/O(K);Trie 插入/查询 O(L),空间按前缀路径数;L 为字符串长度。

概念解释

  • 堆高对数。
  • Trie 按字符步数。
  • 空间分列。

原理流程

  1. 堆操作沿树高。
  2. Trie 逐字符访问。
  3. 辅助空间按规模。

代码 / 图示

堆:O(log n) 操作 / O(n)
Trie:O(L) 操作 / O(前缀路径)

常见误区

  • 误区:Trie 查询 O(1);正解:O(L)。
  • 误区:建堆 O(n log n);正解:自底向上 O(n)。

追问

  • Q:Trie 遍历所有单词? A:O(节点数)。
  • Q:堆建 Top-K 流式? A:O(K) 常驻。

02.4.1.4-020 本知识域常见变体有哪些?

一句话结论

堆:优先队列、Top-K、合并 K 链、中位数双堆;Trie:前缀补全、词频统计、通配匹配、最大异或;主线是父子堆序与字符路径共享。

概念解释

  • 堆:最值维护。
  • Trie:前缀共享。
  • 与其他结构组合。

原理流程

  1. 判断需求是最值还是前缀。
  2. 选堆或 Trie。
  3. 套用对应模板。

代码 / 图示

最值/淘汰:堆
前缀/字典:Trie

常见误区

  • 误区:前缀问题用堆解决;正解:堆不维护字符路径。
  • 误区:最值问题用 Trie;正解:Trie 不快速取全局最值。

追问

  • Q:优先队列底层? A:二叉堆常见。
  • Q:Trie 与并查集结合? A:一般不结合,分属不同场景。