java中priority_queue常用api

常用 API 速查

操作 API 方法 描述 时间复杂度
入队 offer(E e) 或 add(E e) 将元素插入堆中，并自动调整位置。 \(O(\log N)\)
出队 poll() 获取并移除堆顶元素（最小值）。 \(O(\log N)\)
查看 peek() 仅获取堆顶元素（不移除）。 \(O(1)\)
判空 isEmpty() 堆是否为空。 \(O(1)\)
大小 size() 堆中元素个数。 \(O(1)\)
删除 remove(Object o) 删除指定元素（效率较低，不常用）。 \(O(N)\)

初始化与排序规则

通过 Comparator 决定它是小顶堆还是大顶堆。

A. 默认：小顶堆 (Min-Heap)

// 默认构造函数，自然顺序 (从小到大)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

minHeap.offer(10);
minHeap.offer(5);
minHeap.peek(); // 结果是 5

Java

// 默认构造函数，自然顺序 (从小到大)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

minHeap.offer(10);
minHeap.offer(5);
minHeap.peek(); // 结果是 5

B. 修改为：大顶堆 (Max-Heap)

想要堆顶是最大值，需要传入自定义比较器。

// 写法 1: Lambda 表达式 (推荐，最简洁)
// (a, b) -> b - a 表示降序
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);

// 写法 2: 使用库函数 (防止整数溢出，更严谨)
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> Integer.compare(b, a));

// 写法 3: 逆序比较器
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

Java

// 写法 1: Lambda 表达式 (推荐，最简洁)
// (a, b) -> b - a 表示降序
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);

// 写法 2: 使用库函数 (防止整数溢出，更严谨)
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> Integer.compare(b, a));

// 写法 3: 逆序比较器
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

C. 自定义对象排序

比如存一个 int[] 数组，或者 Node 对象。

// 假设存的是 int[] {value, index}
// 我们想根据 value (数组第0位) 进行从小到大排序
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);

C++ vs Java 对照表

特性 C++ (std::priority_queue) Java (java.util.PriorityQueue)
默认顺序 大顶堆 (Max-Heap) 小顶堆 (Min-Heap)
入队 push() offer() / add()
出队 pop() (无返回值) poll() (返回堆顶并删除)
查看堆顶 top() peek()
定义大顶堆 priority_queue<int> new PriorityQueue<>((a,b)->b-a)
定义小顶堆 priority_queue<int, vector<int>, greater<int>> new PriorityQueue<>()

Java

// 假设存的是 int[] {value, index}
// 我们想根据 value (数组第0位) 进行从小到大排序
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);