读完这篇，你能做什么
能为精确定位、范围和最早到期任务分别选结构，并说明复杂度前提。
学习理由、准备要求与知识点
为什么学它
不同结构对精确查找、范围查询和优先级访问提供不同能力与成本。
先读这些内容
知识点清单
- 哈希映射和冲突
- 散列分布与负载
- 稳定键
- 二叉搜索树退化
- 平衡树高度
- 堆的局部顺序
PriorityQueue成本- 比较器等价与业务键
运行前先确认Java 17；源码在本机 Microsoft OpenJDK 17.0.20.1 src.zip 核验，在线链接为上游 jdk-17.0.20-ga。深入模块可在掌握基础后回读。
01先弄懂它是什么
按编号找商品、找一段价格范围、取出当前最紧急的任务，需要的数据结构可能不同。哈希表按哈希值和相等规则找键，适合检查存在或按键取值；搜索树按大小关系组织数据，适合排序和范围查询；堆只维护父子之间的优先级，适合反复取出最小或最大项。能存同样的数据，不代表适合做同样的操作。
哈希表通常查得快，但需要哈希值分布和容量安排得合理。不同键可能得到相同哈希值，这叫冲突；表还会比较真实键，所以冲突不等于数据被丢掉。键加入后若改了参与哈希的字段，就可能查不回原记录；数据增加也可能引发扩容。Java17 HashMap 对部分冲突有额外处理，仍不能忽略键的相等规则和大量碰撞的成本。
普通二叉搜索树在极端插入顺序下可能退化成长链，平衡树通过维护高度约束控制路径长度。TreeMap 基于有序比较，比较结果为零会被当作同一排序键。PriorityQueue 则通常让最小元素在顶部，遍历顺序不保证全局有序；需要排序输出时应逐次移除或显式排序副本。
文中这几个词，先认一认
- 负载因子
- 控制哈希表允许装多满的参数之一，达到相应条件时可能需要扩容。
- 平衡树
- 通过调整结构控制高度的搜索树，避免查一个值时退化成从头走到尾。
- 堆序
- 例如最大堆要求父节点的值不小于它的子节点，就像每位组长的优先级都不低于直接组员。只满足这种父子关系，不代表按普通遍历次序读一遍所有节点，就能得到完整排序。
- Top K
- 只求按某种规则最好的 K 项，例如最贵的 10 件商品，不必把所有数据完整排序。
02看看它怎么工作
完全二叉堆可以按从上到下、每层从左到右的顺序放进数组。下标从零开始时，非根节点 i 的父下标是 (i-1)/2 向下取整；根节点 i=0 没有父节点。左右子节点的候选下标是 2i+1、2i+2，只有小于元素数量时才存在。新元素放到末尾后，沿父节点向上比较和调整，叫上浮；取走堆顶后，把末项放到根，再向下调整。每次主要检查一条上下路径，而堆的层数只随元素数量按对数增长。
只求最大的 k 项时，维护大小最多 k 的最小堆更合适。堆顶是当前候选中最弱的一项，新值若不超过它就不可能进入当前前 k；更大则替换堆顶。这个方向容易记反：要保留最大若干项，内部用最小堆暴露应被淘汰的最小候选。
堆没有保存候选内部完整顺序，所以扫描结束后还需把最多 k 项排序为最终输出。若只需要第 k 大值且候选足够，堆顶就能直接回答；若需要全部结果按降序展示，则这一步成本不能省略。图把候选维护与最终展示分开，防止把 PriorityQueue.iterator 当成排序遍历。
正在加载流程图…
查看流程图源码（Mermaid）
flowchart TD
A["扫描新数值"] --> B{"候选堆未满"}
B -->|"是"| C["加入最小堆"]
B -->|"否"| D{"新值大于堆顶"}
D -->|"是"| E["移除最弱候选并加入新值"]
D -->|"否"| F["忽略新值"]
C --> A
E --> A
F --> A
G["扫描完成"] --> H["取候选并显式降序排序"]按顺序看，每一步做了什么
- 明确需要无序查询、有序范围还是最优项。
- 核对相等或比较器的键语义。
- 为堆写出父子不变量。
- Top K 明确重复与平价策略。
- 把候选维护和输出排序成本分别计算。
03对照实现代码
Microsoft OpenJDK 17.0.20.1；java.base/java/util/PriorityQueue.java · java.util.PriorityQueue#siftUpComparable(int,Object,Object[])
以下为原创 Java 17 教学实现，不是原样 JDK 源码；只保留文中明确讨论的机制，省略优化、兼容及内部接口。
public final class SourceModel {
public static void siftUp(int[] heap, int index) {
int value = heap[index];
int position = index;
while (position > 0) {
int parent = (position - 1) / 2;
if (heap[parent] <= value) break;
heap[position] = heap[parent]; // 较大父值向下，为新值腾出位置。
position = parent;
}
heap[position] = value;
}
}真实 PriorityQueue.siftUpComparable 把元素按自然顺序与父节点比较，父节点优先级不高于当前元素时停止，否则把父项向下移动并继续。模型专门处理 int 数组，省略泛型、比较器路径、容量增长和公开参数校验；调用前要求只有新加入位置到根的堆序可能被破坏。
先保存新 value，再移动父项，避免在搬运过程中丢失新值。每次 position 变为 parent，路径严格向根缩短，最多经过堆高层数。其它子树没有改变，因此只需要修复这条路径，不必每次插入都重新排序整个容器。
自然顺序路径会把元素转换成可比较类型，另一个路径则使用调用者提供的 Comparator。比较规则必须稳定，不能在入堆后修改影响优先级的字段并期待堆自动调整。对可变任务优先级，通常需要明确移除重插或使用带版本的惰性失效策略。
上浮只建立父子关系，无法推出数组从左到右有序。例如根最小成立，两个不同子树之间仍可能交错。源码结构直接解释了为什么 PriorityQueue 的迭代不能当作完整排序输出，以及为什么 peek 只保证当前顶项而非任意下标的有序位置。
代码先调用谁，再调用谁
- offer 追加元素并确保容量
siftUp选择自然顺序或比较器路径- 沿父链移动较大父项
- 把新元素放到恢复堆序的位置
04动手写一个例子
用有界最小堆保留最大的 K 个整数
输入 int 数组与非负 k，返回最大的至多 k 项，保留重复次数并按降序输出。k 大于长度时返回全部排序结果，k 为零或输入空时返回空；不修改输入。
- 输入 1
[3,1,5,5,2]，k=3- 输出 1
[5,5,3]
- 输入 2
[-3,-1,-2]，k=2- 输出 2
[-1,-2]
- 输入 3
任意数组，k=0- 输出 3
[]
把实际候选上限设为 k 与输入长度的较小值，零上限直接返回空。堆未满时加入元素，堆满后只接受比堆顶更大的值。相等值若堆已满可以忽略，因为它不会改变输出多重集合的最佳数值；此前加入的重复项仍被保留。
处理一个前缀后，堆始终包含该前缀最大的 limit 项，或前缀本身不足 limit 的全部项。新值若不大于当前最小候选，就没有理由替换任何候选；若更大，替换最小项正好恢复最佳集合。这个交换论证比只看样本更能说明选择正确。
扫描完成后复制堆中元素并降序排序，明确最终输出顺序。不要直接迭代堆打印并期待降序。时间由 n 次候选判断、可能的对数级调整和最后 k 项排序组成；当 k 接近 n 时，完整排序可能更简单，具体选择取决于后续是否还需要持续输入。
为什么这样写是对的处理任意输入前缀后，堆保存该前缀中最大的 min(limit,前缀长度) 个值，堆顶是候选中最小者。
每个元素最多导致一次插入或替换，堆高度对数；最后对 k 项排序。使用 k+1 书写覆盖 k 为零或一的边界，零上限可直接结束。
保存为 Main.java，运行 javac --release 17 -encoding UTF-8 Main.java，再运行 java Main。程序包含固定输入自测，断言失败时会抛出错误。
展开收起代码 · Main.java · 完整可运行程序
长行可在代码区域内左右滚动，按 Tab 可把焦点移入代码区。
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
public class Main {
static List<Integer> largest(int[] values, int k) {
if (values == null || k < 0) throw new IllegalArgumentException("input");
int limit = Math.min(k,values.length);
if (limit == 0) return List.of();
PriorityQueue<Integer> candidates = new PriorityQueue<>();
for (int value : values) {
if (candidates.size() < limit) candidates.offer(value);
else if (value > candidates.peek()) {
// 堆顶是当前候选中最弱者，只在更优值到来时淘汰。
candidates.poll(); candidates.offer(value);
}
}
List<Integer> output = new ArrayList<>(candidates);
output.sort(Comparator.reverseOrder()); // 堆迭代本身不是排序输出。
return List.copyOf(output);
}
static void check(List<Integer> wanted, int k, int... input) {
if (!wanted.equals(largest(input,k))) throw new AssertionError(wanted);
}
public static void main(String[] args) {
// 重复、负数、零上限、空、超长 k 和整数极值。
check(List.of(5,5,3),3,3,1,5,5,2);
check(List.of(-1,-2),2,-3,-1,-2);
check(List.of(),0,1,2);
check(List.of(),3);
check(List.of(3,2,1),9,1,3,2);
check(List.of(Integer.MAX_VALUE),1,Integer.MIN_VALUE,Integer.MAX_VALUE);
boolean rejected = false;
try { largest(new int[0],-1); } catch (IllegalArgumentException e) { rejected = true; }
if (!rejected) throw new AssertionError("k");
System.out.println("PASS 7");
}
}这些特殊情况也要试一试
- 重复值按出现次数保留。
- 负数不使用零作为默认最佳值。
- k 超出长度返回全部项。
- 不修改原数组，结果结构不可修改。
进阶选读 · 可选深入：多路有序流归并
场景若干来源各自有序，需要持续输出全局最小项。
做法堆中只放每个来源的当前头项，取出后从同一来源补下一项，并用来源序号定义平价顺序。
复杂度处理 N 项、k 个来源通常 O(N log k)，额外 O(k) 候选。
好处与代价来源阻塞和失败需要独立策略，堆只决定已有候选顺序，不解决网络等待与完整性。
05项目里怎么用
只按 ID 找数据，通常不必维护排序树；要查范围、前一项或后一项，则需要有序结构。哈希键在使用期间应保持稳定，树的比较规则也要符合业务对“相同”的定义。换容器可能同时改变遍历顺序和去重结果，不能只核对它们都有同名方法。
优先队列适合调度最早到期或最高优先级候选，但普通 PriorityQueue 不是线程安全队列，也不自动支持优先级动态修改。把任务对象的优先级字段改掉不会重新建立堆序；可以移除重插，或在出队时识别过期版本，具体成本与一致性应明确。
Top K 在日志、榜单和推荐候选中常见，必须定义重复、平价和结果时效。按分数相同就任意丢弃可能不符合用户排名要求，稳定 ID 或时间可以补全排序。输入规模、k 大小和是否持续流入决定堆、排序或选择算法的适用性，不能宣称一种方案永远最快。
容易踩的坑
- 遍历
PriorityQueue时期待全局有序。 - 把普通二叉搜索树自动当作平衡树。
- 修改堆内对象优先级却不重新调整。
- Top K 忘记重复和同分的业务规则。
几种做法，怎么选
表格有四列，窄屏可左右滑动查看代价和适用条件。
| 方案 | 优势 | 代价与限制 | 适用条件 |
|---|---|---|---|
| 哈希表 | 常见键查询期望高效 | 无天然范围顺序且依赖哈希质量 | 映射、去重和成员判断 |
| 平衡搜索树 | 有序与范围操作清楚 | 每次操作有比较和节点成本 | 范围查询、前驱后继 |
| 二叉堆 | 反复取最优项且维护成本低 | 不支持任意位置有序遍历 | 调度、Top K 和多路归并 |
06检验是否读懂了
先自己想、自己写，再展开答案核对。场景题是假设的练习情境；遇到还没学过的内容，可以做完基础后再回来。
先用自己的话解释
01堆序为什么不等于排序？
展开参考答案与推导
它只约束父节点与孩子，两个子树之间没有完整先后关系。根可以保证最优，但数组或迭代顺序不保证有序，需要不断移除或另行排序。
02保留最大 K 为什么用最小堆？
展开参考答案与推导
候选中最小项是最容易被淘汰的边界，放在堆顶可快速判断新值是否值得进入。最大堆暴露的是最强候选，反而不便决定该淘汰谁。
03普通搜索树为什么可能退化？
展开参考答案与推导
若连续按某种顺序插入而不维护平衡，节点可能都落在同一侧，高度接近元素数。平衡树通过旋转或其它结构约束限制高度，不能把普通树的查找无条件写成对数。
换个情况，还会处理吗
01任务优先级改了但出队顺序没变，为什么？
展开参考答案与推导
堆不会自动追踪对象字段变化。需要在受控条件下移除重插或采用版本化候选策略，同时处理并发与重复条目；仅改变字段并未恢复父子堆序。
02同分用户排名每次变化，先补什么规则？
展开参考答案与推导
明确稳定平价键，例如 ID 或创建时间，并在所有比较、Top K 和输出阶段一致使用。只比较分数没有唯一顺序，不能把未定义行为留给容器遍历或线程调度决定。
03k 与 n 一样大，堆是否仍最好？
展开参考答案与推导
不一定。此时维护堆后还要排序所有候选，完整排序可能更简单且常数更合适。结合数据是否流式、内存和实际规模比较，不能只根据 Top K 名字固定选择。
写代码试一试
01求第 K 大而不返回全部
- 输入 / 条件
[3,1,5,5,2]，k=3- 输出 / 预期
3
提示 候选满时堆顶是边界。
展开参考答案与推导
要求一到数组长度的合法 k，扫描后返回最小堆顶即可，不需要最终排序。空输入或 k 超界应拒绝或返回明确缺失，不能沿用“至多 k 项”接口的全部边界。
02验证全相等输入
- 输入 / 条件
[7,7,7,7]，k=2- 输出 / 预期
[7,7]
提示 重复次数应保留。
展开参考答案与推导
加入结果两项七的测试。若使用 Set 维护候选会丢失重复项，说明抽象语义不匹配；算法筛选的是元素多重集合而不是不同值集合。
03返回带ID的候选
- 输入 / 条件
同分A与B，只留一项- 输出 / 预期
按明确ID规则选择
提示 比较器必须形成完整顺序。
展开参考答案与推导
把值改成记录，比较分数后再比较 ID，并让堆顶代表完整规则下最弱项。最终输出用相反或对应的展示顺序，避免候选淘汰规则与展示规则不一致。
读完之后，独立完成
课后作业：自己做一遍
本篇共 10 道作业，先完成 8 道基础与综合任务，再按前置知识挑战进阶题。其中包含 1 道思维拓展，试着换个条件，看看原来的办法是否还管用。不附参考答案。
能为精确定位、范围和最早到期任务分别选结构，并说明复杂度前提。
本篇重点加练
重点训练稳定键与比较器等价，让不同索引对同一业务对象采用一致身份政策。
- 稳定键
- 比较器等价与业务键
重点内容会多练几次。先说清楚怎么做，再试试空数据、出错或条件改变时会发生什么。
先自己做，卡住时记下问题，再回来查。问答题写清“为什么、什么时候适用”；动手题留下输入、输出和运行步骤，方便下次重做。
基础必做
- 作业 01原理问答
为学生编号查询设计哈希映射，比较均匀键、集中碰撞键和可变键三组输入。说明每组需要验证的正确性与成本，不用“平均
O(1)”覆盖全部情况。- 提交内容
- 键合同与三组实验计划。
- 怎样算完成
- 哈希分布前提明确
- 键稳定性单独检查
练到的知识点哈希映射和冲突 · 散列分布与负载 · 稳定键
- 作业 02代码推演
把 [1,2,3,4,5] 和 [3,1,5,2,4] 分别插入普通二叉搜索树，画出形状并计算查找路径；说明平衡约束需要控制哪项结构指标。
- 提交内容
- 两棵树与路径长度表。
- 怎样算完成
- 有序性质和高度分开
- 操作成本与结构对应
练到的知识点二叉搜索树退化 · 平衡树高度
综合应用
- 作业 03排错实验
向
PriorityQueue插入 [7,2,9,2,5]，分别记录迭代次序、peek 结果和连续 poll 的结果；对每种操作说明接口实际承诺。- 提交内容
- Java 实验、自写重复值与空队列测试、运行证据。
- 怎样算完成
- 遍历与逐次出队语义分开
- 成本区分单次与全部操作
练到的知识点堆的局部顺序 · PriorityQueue 成本
- 作业 04设计评审
排行榜以分数比较学生，存在两个同分不同 ID。分别为
TreeSet、HashMap和PriorityQueue定义如何识别学生、处理同分及更新记录。- 提交内容
- 三种结构的键/比较器设计及验收样本。
- 怎样算完成
- 比较器零值语义明确
- 结构选择服务具体操作
练到的知识点比较器等价与业务键
- 作业 05编程实践
实现最多保留 3 个最高分候选的排行榜，候选含不可变 ID 与分数，平分按先约定的 ID 顺序；输入含重复 ID，需先决定更新政策。
- 提交内容
- Java 实现、自写平分/重复/少量输入测试及运行证据。
- 怎样算完成
- 业务更新与堆维护一致
- 结果顺序有合同
- 时间空间按输入和容量说明
练到的知识点稳定键 · 堆的局部顺序 · PriorityQueue 成本 · 比较器等价与业务键
- 作业 06编程实践
为收藏文章实现按编号查询与按标题排序两个视图，标题允许相同且可更新；规定文章身份后写测试核对两视图是否指向同一业务集合。
- 提交内容
- Java 实现、自写同名/标题更新/删除测试与运行证据。
- 怎样算完成
- 业务键保持声明的稳定性
- 视图一致性有独立核验
练到的知识点稳定键 · 比较器等价与业务键
- 作业 07设计评审
用户编号未来可能合并，旧编号仍需查询历史数据。设计稳定键与别名关系，说明
Map键是否应直接随显示编号变化。- 提交内容
- 身份模型和编号合并验收。
- 怎样算完成
- 历史引用的含义明确
- 变更操作有一致性边界
练到的知识点稳定键
- 作业 08代码推演
比较器仅使用名字时与同时使用名字和编号时，分别插入同名不同编号对象；预先声明集合的业务去重合同，再观察实际行为。
- 提交内容
- 比较器、样本和契约对照记录。
- 怎样算完成
- 排序等价与业务唯一性逐项比较
- 没有用正常排序样本替代碰撞样本
练到的知识点比较器等价与业务键
进阶挑战 · 掌握前置后选做
- 作业 09面试场景
完成性能分析后：外部输入可制造大量重复或碰撞，系统需支持精确查询、范围查询与实时优先级。提出组合数据结构的评审方案，说明维护一致性的代价。
- 提交内容
- 操作需求矩阵、资源预算与失效场景。
- 怎样算完成
- 每个结构承担明确操作
- 多索引更新原子边界清楚
练到的知识点散列分布与负载 · 二叉搜索树退化 · 堆的局部顺序 · PriorityQueue 成本
思维拓展
先写出你的猜想，再用例子或实验验证。答案可以不同，但要说清依据、适用情况，以及还有什么没弄懂。
- 作业 10思维拓展 · 跨域迁移
把内存有序集合替换成数据库唯一索引加排序查询。审查大小写、空值和平价规则是否仍表达相同身份，尚未学数据库可用表格模拟。
- 提交内容
- 两种模型对应与冲突样本。
- 怎样算完成
- 跨表示的比较政策明确
- 相同标签不被视为自动相同语义
练到的知识点稳定键 · 比较器等价与业务键
完成后，再检验一次
给每题标记“独立完成 / 查阅后完成 / 尚未完成”。查过资料或没做出的题，记下卡在哪里。隔一天换一组输入再试，能解释结果和出错原因，再把这个知识点标为掌握。
继续阅读
先看能帮你完成当前练习的部分。例子跑通后，再读更深入的解释。
- 必读教程英文
Harvard CS50：数据结构 （新标签页）↗
阅读数组、链表、栈队列、树与哈希表；C 指针示例只用于理解结构，练习以 Java 17 改写。
- 实践参考文档英文
Java 17 API：HashMap （新标签页）↗
阅读散列分布、迭代、fail-fast 与非线程安全前提，区分实现和约定。
- 深入参考文档英文
Java 17 API：TreeMap （新标签页）↗
阅读有序映射、红黑树复杂度和比较器与 equals 一致性的要求。
- 深入参考文档英文
Java 17 API：PriorityQueue （新标签页）↗
阅读堆顶访问、入队出队复杂度与迭代器无排序保证的说明。
- 实践实践指南中文
Hello 算法：用图和 Java 理解数组、链表与查找 （新标签页）↗
先读第 2 章和第 4—6 章，再读二分查找。小练习：在五个数字的数组中插入一个数，先画出移动过程，再用 Java 实现；说明容量不够时怎么办。 正文和代码公开，部分可视化依赖外部工具。教材支持多种语言，建议先固定 Java 学习。
- 深入参考文档英文
OpenJDK 17u java.util.PriorityQueue （新标签页）↗
定位
PriorityQueue.siftUpComparable的父链比较与搬移，模型专门展示int上浮。 - 深入参考文档英文
Princeton 优先队列 （新标签页）↗
学习堆序、上浮下沉和优先队列应用。
- 深入参考文档英文
Princeton 平衡搜索树 （新标签页）↗
理解限制树高与有序查找的关系。
- 深入参考文档英文
Princeton 哈希表 （新标签页）↗
阅读散列、冲突和负载策略的成本前提。