Top K问题与小顶堆原理
Top K问题指的是从大量数据中找出最大或最小的K个元素，比如从100万条用户积分数据中找出积分最高的前100名。如果直接对全量数据排序，时间复杂度是O(nlogn)，当数据量极大时效率很低。而小顶堆是一种特殊的完全二叉树结构，堆顶元素始终是堆中最小的元素，利用这个特性可以高效处理Top K问题。
处理最大的K个元素时，我们可以维护一个大小为K的小顶堆：遍历数据时，如果堆的大小还没到K，直接把元素加入堆；如果堆已经满了，就比较当前元素和堆顶元素，如果当前元素比堆顶大，就弹出堆顶，把当前元素加入堆。遍历结束后，堆里的元素就是最大的K个元素。
Java PriorityQueue实现小顶堆
Java中的PriorityQueue默认就是小顶堆结构，底层基于数组实现，默认初始容量是11，元素按照自然顺序排序，也可以通过自定义比较器调整排序规则。需要注意的是PriorityQueue是线程不安全的，多线程场景下需要使用PriorityBlockingQueue。
基础使用示例
下面先看一个简单的PriorityQueue基础使用示例，展示小顶堆的基本操作：
import java.util.PriorityQueue;
public class PriorityQueueDemo {
public static void main(String[] args) {
// 创建默认小顶堆，存储整数
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
// 添加元素
minHeap.add(5);
minHeap.add(1);
minHeap.add(3);
minHeap.add(2);
minHeap.add(4);
// 依次弹出堆顶元素，输出顺序是从小到大
while (!minHeap.isEmpty()) {
System.out.println(minHeap.poll());
}
}
}
上述代码运行后会依次输出1、2、3、4、5，说明PriorityQueue默认确实按照升序排列，堆顶是最小元素。
用PriorityQueue实现Top K问题
接下来我们实现从海量整数中找出最大的前K个元素的完整逻辑，这里模拟10万条随机数据，找出最大的前5个元素：
import java.util.PriorityQueue;
import java.util.Random;
public class TopKDemo {
public static void main(String[] args) {
int k = 5; // 需要找的前K个最大元素
int dataSize = 100000; // 模拟的海量数据量
// 创建小顶堆，大小为K
PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
Random random = new Random();
// 遍历所有数据
for (int i = 0; i < dataSize; i++) {
int num = random.nextInt(1000000); // 生成0到999999的随机数
if (minHeap.size() < k) {
// 堆还没满，直接加入
minHeap.add(num);
} else {
// 堆满了，比较当前元素和堆顶元素
if (num > minHeap.peek()) {
minHeap.poll(); // 弹出堆顶最小元素
minHeap.add(num); // 加入当前更大的元素
}
}
}
// 输出结果，堆中元素就是最大的K个，这里从大到小输出
System.out.println("最大的" + k + "个元素是：");
// 因为是小顶堆，需要倒序输出
Integer[] result = new Integer[k];
for (int i = k - 1; i >= 0; i--) {
result[i] = minHeap.poll();
}
for (int num : result) {
System.out.print(num + " ");
}
}
}
自定义对象场景的Top K实现
实际开发中更多场景是处理自定义对象，比如从订单列表中找出金额最高的前10个订单，这时候需要自定义比较器，让PriorityQueue按照订单金额排序：
import java.util.PriorityQueue;
class Order {
private String orderId;
private double amount;
public Order(String orderId, double amount) {
this.orderId = orderId;
this.amount = amount;
}
public double getAmount() {
return amount;
}
@Override
public String toString() {
return "Order{orderId='" + orderId + "', amount=" + amount + "}";
}
}
public class CustomObjectTopK {
public static void main(String[] args) {
int k = 3; // 找金额最高的前3个订单
// 创建小顶堆，自定义比较器，按照订单金额升序排列
PriorityQueue<Order> minHeap = new PriorityQueue<>(k, (o1, o2) -> Double.compare(o1.getAmount(), o2.getAmount()));
// 模拟订单数据
Order[] orders = new Order[]{
new Order("001", 199.9),
new Order("002", 599.9),
new Order("003", 399.9),
new Order("004", 799.9),
new Order("005", 299.9)
};
// 处理数据
for (Order order : orders) {
if (minHeap.size() < k) {
minHeap.add(order);
} else {
if (order.getAmount() > minHeap.peek().getAmount()) {
minHeap.poll();
minHeap.add(order);
}
}
}
// 输出结果
System.out.println("金额最高的" + k + "个订单是：");
while (!minHeap.isEmpty()) {
System.out.println(minHeap.poll());
}
}
}
性能对比与注意事项
我们对比两种处理Top K的方式：
| 处理方式 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 全量排序后截取前K个 | O(nlogn) | O(n) | 数据量小，内存充足 |
| PriorityQueue小顶堆 | O(nlogK) | O(K) | 海量数据，内存有限 |
使用PriorityQueue处理Top K问题时需要注意：
- 如果需要找最小的K个元素，只需要把比较逻辑反过来，或者直接使用默认小顶堆，最后堆里的就是最小的K个元素。
PriorityQueue的peek方法不会移除元素，poll方法会移除并返回堆顶元素，使用时不要混淆。- 自定义比较器时要确保排序逻辑正确，否则会导致堆结构不符合预期，得到错误的结果。
总结
Java中的PriorityQueue实现的小顶堆是处理Top K问题的高效方案，尤其适合海量数据场景，相比全量排序能大幅降低时间和空间开销。核心思路是维护一个大小为K的小顶堆，遍历数据时动态调整堆结构，最终堆中的元素就是目标Top K结果。实际使用时根据数据类型选择默认排序或者自定义比较器即可，注意区分堆的操作方法，避免逻辑错误。
JavaPriorityQueueTop_K小顶堆修改时间：2026-07-12 09:36:27