02.4.1.4 堆与 Trie 树
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.4 树与图 / 02.4.1 二叉树与遍历
02.4.1.4-001 堆在树形结构中处于什么位置?
一句话结论
堆是满足堆序的完全二叉树,通常数组存储;与 BST 不同,堆只保证父子大小关系,兄弟无序;用于优先队列与 Top-K,详细操作见 02.3.2.4。
概念解释
- 堆序:父 ≥ 子(大顶)或父 ≤ 子(小顶)。
- 完全二叉树。
- 不全局有序。
原理流程
- 数组按层序存树。
- 插入上浮、删除下沉维护堆序。
- 堆顶为最值。
代码 / 图示
大顶堆:根最大,兄弟无序
常见误区
- 误区:堆是排序树;正解:只维护堆顶最值。
- 误区:堆必须链表存储;正解:完全树用数组最紧凑。
追问
- Q:堆与 BST 区别? A:堆父子有序、兄弟无序;BST 中序有序。
- Q:堆支持查找任意值? A:不支持高效查找。
02.4.1.4-002 堆的数组下标怎么映射?
一句话结论
下标 0 起:父 (i-1)/2,左孩子 2i+1,右孩子 2i+2;完全二叉树无空洞,数组紧凑存储;孩子越界需判断。
概念解释
- 层序编号。
- 父子公式。
- 边界判断。
原理流程
- 根下标 0。
- 按层序填数组。
- 公式定位父子。
代码 / 图示
父:(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);大顶堆上浮到父更大为止。
概念解释
- 末尾插入。
- 上浮维护堆序。
- 沿父链上移。
原理流程
- 追加末尾。
- 与父比较。
- 违反则交换上移。
代码 / 示例
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);大顶堆选较大孩子交换。
概念解释
- 堆顶移除。
- 末尾补位。
- 下沉恢复堆序。
原理流程
- 堆顶 = 末尾。
- 规模减一。
- 选孩子比较交换下沉。
代码 / 示例
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)。
概念解释
- 自底向上。
- 层代价求和。
- 线性收敛。
原理流程
- 从最后非叶子向前。
- 逐个下沉。
- 各层步数求和。
代码 / 图示
Σ 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) 额外空间,不稳定。
概念解释
- 堆顶最大值。
- 交换到末尾固定。
- 剩余堆下沉恢复。
原理流程
- 原地建大顶堆。
- 堆顶换末尾。
- 规模减一,下沉堆顶。
代码 / 图示
大顶堆 → 最大值在根 → 换末尾 → 剩余下沉
常见误区
- 误区:堆排序稳定;正解:跨距交换不稳定。
- 误区:建堆 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。
- 堆顶为淘汰边界。
- 超界替换。
原理流程
- 先放 K 个入堆。
- 后续与堆顶比较。
- 更优则替换下沉。
代码 / 示例
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 是按字符串前缀共享路径的多叉树:边代表字符,节点代表前缀;根为空串,节点可标记单词结束;支持插入、查询、前缀匹配。
概念解释
- 路径:字符序列。
- 共享:公共前缀合并。
- 结束标记:区分前缀与完整单词。
原理流程
- 根出发按字符走边。
- 缺边则新建节点。
- 单词末尾打标记。
代码 / 图示
根 → c → a → t(结束)
→ b(结束)
常见误区
- 误区:Trie 节点存完整字符串;正解:节点存字符/子节点映射,路径拼词。
- 误区:无结束标记也能判断完整单词;正解:前缀不等于单词。
追问
- Q:Trie 适用字符集? A:小写字母用数组,大字符集用哈希映射。
- Q:与哈希表比前缀能力? A:Trie 天然支持前缀遍历。
02.4.1.4-009 Trie 插入怎么做?
一句话结论
从根按单词字符逐位查找,缺子节点则新建;走到末尾标记单词结束;O(L) 时间,L 为单词长度。
概念解释
- 逐字符走边。
- 缺边新建。
- 结束标记。
原理流程
- 指针从根开始。
- 每字符查子节点,缺则建。
- 末尾置 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,才是完整单词;仅路径存在只说明是前缀。
概念解释
- 路径存在 ≠ 单词结束。
- 结束标记判定。
- 中途失败。
原理流程
- 逐字符查子节点。
- 缺边返回 false。
- 末尾检查 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)。
概念解释
- 前缀节点:子树根。
- 子树遍历收集。
- 共享前缀复用。
原理流程
- 走到前缀节点。
- 遍历子树拼路径。
- 收集 end 节点单词。
代码 / 图示
前缀 "ca" 子树 → cat, cab, cap ...
常见误区
- 误区:前缀匹配只查单节点;正解:需遍历子树枚举单词。
- 误区:收集非 end 路径;正解:只收完整单词。
追问
- Q:自动补全用什么? A:Trie 子树遍历 + 热度排序。
- Q:前缀计数? A:节点维护经过次数。
02.4.1.4-012 Trie 删除怎么做?
一句话结论
先确认单词存在,再逆序删除无子节点且非结束标记的节点;被删单词若为其他词前缀,只清除 end 标记不删路径;O(L) 时间。
概念解释
- 逆序清理。
- 共享路径保留。
- 标记与节点区分。
原理流程
- 查找路径记录节点。
- 清除末尾 end。
- 逆序删空叶子,有共享则停。
代码 / 图示
cat 存在,car 共享 ca 路径
删 cat:删 t,保留 c-a
常见误区
- 误区:删除整条路径影响共享词;正解:有子节点或 end 则保留。
- 误区:单词不存在也删;正解:先校验存在性。
追问
- Q:迭代删除? A:栈记录路径逆序处理。
- Q:Trie 适合频繁删除吗? A:可做,空间回收需判断共享。
02.4.1.4-013 Trie 节点怎么维护词频与前缀计数?
一句话结论
节点维护 count(经过该前缀的单词数)与 endCount(以该节点结束的单词数);插入时沿途累加,删除时递减;可统计前缀出现次数。
概念解释
- 前缀计数:沿途经过次数。
- 词频:结束节点计数。
- 增量维护。
原理流程
- 插入沿途 count++,末尾 endCount++。
- 查询直接读计数。
- 删除对应递减。
代码 / 图示
node.pass:经过前缀次数
node.end:结束单词数
常见误区
- 误区:只记结束计数无法求前缀频次;正解:沿途 pass 计数。
- 误区:重复插入未累加;正解:重复词频递增。
追问
- Q:前 K 热词? A:计数 + 堆遍历子树。
- Q:删除计数归零处理? A:标记空闲可回收。
02.4.1.4-014 Trie 与哈希表怎么对比?
一句话结论
哈希表按键整体哈希 O(L) 插入查询,不支持前缀;Trie 按字符共享前缀,支持前缀匹配、自动补全与字典序遍历;前缀密集场景 Trie 更省重复存储。
概念解释
- 哈希:整键散列。
- Trie:路径共享。
- 前缀能力差异。
原理流程
- 看是否需要前缀查询。
- 看字符集与重复度。
- 选型。
代码 / 图示
精确取值:哈希 O(L)
前缀/补全:Trie
常见误区
- 误区:Trie 查询 O(1);正解:O(L),L 为串长。
- 误区:Trie 空间恒优于哈希;正解:稀疏字符集下节点开销大。
追问
- Q:大字符集 Trie 怎么省空间? A:压缩 Trie/哈希映射子节点。
- Q:字典序遍历? A:Trie 子节点按序遍历。
02.4.1.4-015 Trie 空间复杂度怎么算?
一句话结论
最坏 O(字符集 × 总字符数),共享前缀后实际节点数等于所有单词不同前缀路径数;数组子节点按字符集定宽,哈希映射按需建子节点。
概念解释
- 节点数:不同前缀。
- 每节点子节点开销。
- 共享降低节点数。
原理流程
- 统计插入后不同前缀。
- 单节点子节点结构开销。
- 合计空间。
代码 / 图示
无共享:Σ 单词长度
有共享:不同前缀路径数
常见误区
- 误区:Trie 空间 O(单词数);正解:按字符路径计。
- 误区:26 数组无空开销;正解:空引用也占节点内数组空间。
追问
- Q:压缩前缀树? A:单链路径合并成边,省节点。
- Q:超长公共前缀收益? A:共享越多越省。
02.4.1.4-016 Trie 怎么支持通配符匹配?
一句话结论
查询遇通配符(如 .)遍历当前节点所有子节点递归匹配;普通字符走对应子节点;O(字符集^匹配位置) 最坏,通常剪枝。
概念解释
- 通配:多分支。
- 递归逐字符。
- 结束标记判定。
原理流程
- 普通字符走唯一子边。
- 通配遍历全部子节点。
- 末尾检查 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 的结合考点。
概念解释
- 位路径:高位到低位。
- 贪心反位。
- 异或最大值。
原理流程
- 数按位插入 0/1 树。
- 查询每位优先选反位。
- 拼出最大异或值。
代码 / 图示
高位优先:反位异或为 1
常见误区
- 误区:按十进制字符建 Trie;正解:按二进制位分支。
- 误区:低位优先;正解:高位对结果贡献最大。
追问
- Q:位数固定多少? A:按数值范围定 30/31 位。
- Q:离线排序替代? A:分治求异或对,Trie 更直接。
02.4.1.4-018 堆与 Trie 题有哪些边界用例?
一句话结论
空输入、单元素、全相同值、字符空串、单字符单词、前缀即完整单词、重复插入、字符集越界;判空、结束标记与计数口径。
概念解释
- 空与最短。
- 等值/重复。
- 前缀与单词重叠。
原理流程
- 空结构返回默认。
- 单元素走边界分支。
- 标记与计数复核。
代码 / 图示
空堆 / 单元素
"" / "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 按字符步数。
- 空间分列。
原理流程
- 堆操作沿树高。
- Trie 逐字符访问。
- 辅助空间按规模。
代码 / 图示
堆: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:前缀共享。
- 与其他结构组合。
原理流程
- 判断需求是最值还是前缀。
- 选堆或 Trie。
- 套用对应模板。
代码 / 图示
最值/淘汰:堆
前缀/字典:Trie
常见误区
- 误区:前缀问题用堆解决;正解:堆不维护字符路径。
- 误区:最值问题用 Trie;正解:Trie 不快速取全局最值。
追问
- Q:优先队列底层? A:二叉堆常见。
- Q:Trie 与并查集结合? A:一般不结合,分属不同场景。