数据结构与算法 / 系统课时
封装可复用算法组件
封装可复用算法组件
算法进入公共代码库后,正确结果只是最低要求,还要明确参数、排序规则、输入是否会被修改以及结果能否被外部篡改。本课将把 Top K 选择封装成可复用的泛型组件。
学习目标
- 设计与具体业务类型解耦的算法接口
- 明确参数校验、比较器方向和边界行为
- 使用大小为
k的堆返回不可变 Top K 结果
从算法实现到组件契约
公共组件应把调用方必须决定的策略放进接口,而不是写死在实现中。Top K 选择需要输入列表、数量 k 和比较器;比较器定义“更大”代表更优,返回结果按从优到弱排列。
组件还要说明是否允许 null、k=0 如何处理、是否修改原列表,以及返回集合能否被修改。契约越明确,调用方越不需要阅读内部代码猜测行为。

堆如何保留 Top K
遍历元素时,用小顶堆保存当前最优的 k 个值。堆顶是其中最弱的元素;新值更优时,删除堆顶并加入新值。遍历完成后再按比较器逆序排序,因为优先队列的迭代顺序不等于完整有序结果。
该方案遍历 n 个元素,每次堆调整最多需要 ,总时间复杂度为 ,额外空间为 。当 k 远小于 n 时,通常比复制全部数据后排序更合适。
主示例
下面的 Java 17 示例用泛型和比较器封装 Top K。实现不修改输入列表,拒绝 null 元素和越界的 k,并通过 List.copyOf 返回不可修改的结果结构。
java
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
public class ReusableAlgorithmComponentDemo {
private record Product(String name, int score) {
}
private static final class TopKSelector<T> {
List<T> select(List<T> values, int k, Comparator<? super T> comparator) {
// 公共组件尽早校验契约,避免在比较器或堆操作中延迟失败。
if (values == null) {
throw new IllegalArgumentException("输入列表不能为空");
}
if (comparator == null) {
throw new IllegalArgumentException("比较器不能为空");
}
if (k < 0 || k > values.size()) {
throw new IllegalArgumentException("k 超出范围");
}
// 小顶堆的堆顶始终是当前 Top K 中最弱的元素。
PriorityQueue<T> heap = new PriorityQueue<>(Math.max(1, k), comparator);
for (T value : values) {
if (value == null) {
throw new IllegalArgumentException("元素不能为 null");
}
if (heap.size() < k) {
heap.offer(value);
} else if (k > 0 && comparator.compare(value, heap.peek()) > 0) {
heap.poll();
heap.offer(value);
}
}
// 堆的迭代顺序不保证全局有序,返回前必须显式排序。
List<T> result = new ArrayList<>(heap);
result.sort(comparator.reversed());
return List.copyOf(result);
}
}
public static void main(String[] args) {
List<Product> products = List.of(
new Product("A", 90),
new Product("B", 75),
new Product("C", 95),
new Product("D", 88)
);
Comparator<Product> byScoreThenName =
Comparator.comparingInt(Product::score).thenComparing(Product::name);
List<Product> result =
new TopKSelector<Product>().select(products, 3, byScoreThenName);
System.out.println("Top 3:");
for (Product product : result) {
System.out.println(product.name() + ": " + product.score());
}
// 通过一次失败的修改验证结果结构不可变。
boolean immutable;
try {
result.add(new Product("E", 100));
immutable = false;
} catch (UnsupportedOperationException exception) {
immutable = true;
}
System.out.println("结果不可修改: " + immutable);
System.out.println("输入顺序未改变: " + products.get(0).name().equals("A"));
}
}将代码保存为 ReusableAlgorithmComponentDemo.java,再编译运行:
bash
javac ReusableAlgorithmComponentDemo.java
java ReusableAlgorithmComponentDemo预期输出:
text
Top 3:
C: 95
A: 90
D: 88
结果不可修改: true
输入顺序未改变: true边界与交付检查
k=0 应返回空列表,k=values.size() 应返回全部元素的有序副本。同分规则由比较器决定,必须写入文档并通过测试固定下来。返回列表不可修改,不代表其中的元素自动不可变;若元素是可变对象,调用方仍可能改变其内部状态。
发布公共组件前,应测试正常结果、空列表、边界 k、非法参数、同分顺序、输入未修改和结果不可修改。还应注明线程安全性:本实现每次调用只使用局部状态,组件本身无共享可变字段。
按自己的节奏,确认真正理解。