数据结构综合
本节目标
拆分多种数据结构的职责，并用同步不变量保证查询、顺序与动态最值协同工作。
单一数据结构通常只擅长维护一种关系：哈希表擅长定位，链表擅长改写顺序，堆擅长取得边界最值。当题目同时要求多种关系时，正确做法不是让其中一个结构承担全部职责，而是拆分状态，并规定每次更新后它们必须共同满足的不变量。
何时需要组合结构
当一次操作既要按键快速找到对象，又要调整对象的相对顺序；既要维护多路候选，又要持续取出全局最小值；或既要保留两个有序部分，又要随时报告中间边界时，单一结构就不够用了。
组合结构的判断标准是：题目中的不同查询依赖不同的访问方式，而且每种方式都必须在更新后立即保持正确。先写出每种查询需要的关系，再为它选择最小职责的结构。
职责拆分
快速定位＋顺序维护
LRU 缓存同时需要按键查找和维护最近使用顺序。哈希表保存“键 → 节点”，负责 O(1) 定位；双向链表保存从最近到最久未使用的顺序，负责把节点移到表头或从表尾淘汰。两者存的是同一批节点，任何插入、访问和删除都必须同步更新。
这个模型把哈希表的快速定位与链表的重接边组合起来：映射不能指向已删除节点，链表中的每个真实节点也必须能被映射找到。
多个候选源＋动态取最值
合并 K 个有序链表时，每条链表都提供一个当前候选。优先队列只保存每一路尚未处理部分的头节点；取出全局最小节点后，再把该节点的后继加入。这样堆负责在多个候选源中动态取最小值，链表负责保留每一路的后继关系。
这是堆与优先队列的多路候选模型：堆中不需要保存所有节点，只需保存每一路下一次可能成为答案的边界。
两个有序部分＋平衡边界
数据流中位数把较小的一半放入大根堆，把较大的一半放入小根堆。两个堆分别有序，且元素数量之差不超过一；因此堆顶总是中位数所在的边界。每加入一个数，先放入合适的一侧，再把堆顶移动到另一侧以恢复大小关系和数量平衡。
这里的答案不是某个堆维护的全局排序，而是两个有序部分之间的平衡边界。先保证左侧所有元素不大于右侧所有元素，再保证两侧大小差至多为一。
同步不变量
组合结构的更新应按固定检查清单完成：
- 明确本次操作涉及哪些结构，以及每个结构负责的查询；
- 先保存会被改写连接或移出边界的对象，避免失去后续入口；
- 在所有结构中完成插入、删除或移动，不能只更新其中之一；
- 检查跨结构关系：映射是否仍指向有效节点、堆是否仍只含候选边界、两个部分是否仍有序且平衡；
- 最后再返回查询结果，确保结果来自已经恢复的不变量。
把这些条件写成循环或操作后的断言，比只记住某个容器的 API 更可靠。组合题的错误大多来自状态不同步，而不是单个操作本身不会写。
母题序列
按拓展顺序练习四道题；它们分别覆盖定位与顺序、对象关系复制、多路最值和双边界平衡：
- LRU 缓存 拓展：用哈希表定位节点，再用双向链表维护最近使用顺序。
- 随机链表的复制 拓展：用映射建立旧节点与新节点的对应，再同步补齐
next与random关系。 - 合并 K 个升序链表 拓展：让堆维护每一路当前候选，持续取出全局最小节点。
- 数据流的中位数 拓展：用两个堆维护两个有序部分及其平衡边界。
常见误区
- 只把节点从链表中删除，却没有从哈希表中移除，留下悬空或过期映射。
- 把所有链表节点一次性压入堆，忽略“每一路一个候选”能带来的空间与语义优势。
- 两个堆只做数量平衡，却没有修复左侧最大值不大于右侧最小值的边界关系。
- 复制随机链表时只复制
next，或用节点值代替节点对象作为映射键；节点值可以重复。 - 更新多个结构后才临时猜测答案，没有先恢复同步不变量。
迁移方向
组合结构的思想还能迁移到更多在线问题：用映射加有序集合维护可更新的排名，用双端队列加单调性维护滑动窗口最值，用多个队列或堆协调调度优先级。迁移时先拆分“定位、顺序、边界、统计”各自的职责，再为跨结构关系写出能在每次更新后检查的不变量。