当前位置：首页 > news >正文

基于二叉堆实现的 PriorityQueue

news 来源：原创 2025/9/18 12:30:17

基于二叉堆实现的 PriorityQueue 是一种常见的数据结构，广泛用于任务调度、路径搜索、事件模拟等场景。下面我将用 Java 语言实现一个简单的基于最小堆的 PriorityQueue，即优先级最小的元素先出队。

✅ 实现目标

使用数组实现二叉最小堆（即父节点 ≤ 子节点）
支持以下基本操作：
- add(E element)
- peek()
- poll()
- size()
- 自动扩容

🚀 实现代码（Java）

import java.util.Arrays;
import java.util.NoSuchElementException;public class MyPriorityQueue<E extends Comparable<E>> {private static final int DEFAULT_CAPACITY = 16;private Object[] heap;private int size;public MyPriorityQueue() {heap = new Object[DEFAULT_CAPACITY];size = 0;}public void add(E element) {if (element == null) throw new NullPointerException();ensureCapacity();heap[size] = element;siftUp(size);size++;}public E peek() {if (size == 0) throw new NoSuchElementException();return elementAt(0);}public E poll() {if (size == 0) throw new NoSuchElementException();E result = elementAt(0);heap[0] = heap[size - 1];heap[size - 1] = null;size--;siftDown(0);return result;}public int size() {return size;}private void ensureCapacity() {if (size >= heap.length) {heap = Arrays.copyOf(heap, heap.length * 2);}}private void siftUp(int index) {Object temp = heap[index];while (index > 0) {int parent = (index - 1) / 2;if (((E) temp).compareTo(elementAt(parent)) >= 0) break;heap[index] = heap[parent];index = parent;}heap[index] = temp;}private void siftDown(int index) {Object temp = heap[index];int half = size / 2;while (index < half) {int left = 2 * index + 1;int right = left + 1;int smallest = left;if (right < size && elementAt(right).compareTo(elementAt(left)) < 0) {smallest = right;}if (((E) temp).compareTo(elementAt(smallest)) <= 0) break;heap[index] = heap[smallest];index = smallest;}heap[index] = temp;}@SuppressWarnings("unchecked")private E elementAt(int index) {return (E) heap[index];}
}

📦 示例用法

public class Main {public static void main(String[] args) {MyPriorityQueue<Integer> pq = new MyPriorityQueue<>();pq.add(5);pq.add(2);pq.add(9);pq.add(1);while (pq.size() > 0) {System.out.println(pq.poll());}}
}

输出：

如果你需要最大堆版本，只需把比较逻辑反过来即可。

下面是对上面代码的扩展版本，支持传入自定义的 Comparator，从而实现更灵活的排序逻辑，比如最大堆、自定义字段排序等。

✅ 改造目标

支持传入 Comparator<E>，代替 Comparable<E> 进行元素比较。
如果未传入 Comparator，则默认使用元素的自然顺序（即要求 E implements Comparable<E>）。

🚀 改造后的 Java 实现：支持 Comparator 的 PriorityQueue

import java.util.Arrays;
import java.util.Comparator;
import java.util.NoSuchElementException;public class MyPriorityQueue<E> {private static final int DEFAULT_CAPACITY = 16;private Object[] heap;private int size;private final Comparator<? super E> comparator;public MyPriorityQueue() {this(null);}public MyPriorityQueue(Comparator<? super E> comparator) {this.comparator = comparator;this.heap = new Object[DEFAULT_CAPACITY];this.size = 0;}public void add(E element) {if (element == null) throw new NullPointerException();ensureCapacity();heap[size] = element;siftUp(size);size++;}public E peek() {if (size == 0) throw new NoSuchElementException();return elementAt(0);}public E poll() {if (size == 0) throw new NoSuchElementException();E result = elementAt(0);heap[0] = heap[size - 1];heap[size - 1] = null;size--;siftDown(0);return result;}public int size() {return size;}private void ensureCapacity() {if (size >= heap.length) {heap = Arrays.copyOf(heap, heap.length * 2);}}private void siftUp(int index) {Object temp = heap[index];while (index > 0) {int parent = (index - 1) / 2;if (compare((E) temp, elementAt(parent)) >= 0) break;heap[index] = heap[parent];index = parent;}heap[index] = temp;}private void siftDown(int index) {Object temp = heap[index];int half = size / 2;while (index < half) {int left = 2 * index + 1;int right = left + 1;int smallest = left;if (right < size && compare(elementAt(right), elementAt(left)) < 0) {smallest = right;}if (compare((E) temp, elementAt(smallest)) <= 0) break;heap[index] = heap[smallest];index = smallest;}heap[index] = temp;}@SuppressWarnings("unchecked")private E elementAt(int index) {return (E) heap[index];}private int compare(E a, E b) {if (comparator != null) {return comparator.compare(a, b);}return ((Comparable<? super E>) a).compareTo(b);}
}

📦 示例用法

✅ 默认最小堆

MyPriorityQueue<Integer> pq = new MyPriorityQueue<>();
pq.add(4);
pq.add(1);
pq.add(7);
System.out.println(pq.poll()); // 输出 1

✅ 最大堆（传入自定义 Comparator）

MyPriorityQueue<Integer> maxHeap = new MyPriorityQueue<>((a, b) -> b - a);
maxHeap.add(4);
maxHeap.add(1);
maxHeap.add(7);
System.out.println(maxHeap.poll()); // 输出 7

✅ 自定义对象排序（按年龄升序）

class Person {String name;int age;Person(String name, int age) { this.name = name; this.age = age; }public String toString() {return name + "(" + age + ")";}
}MyPriorityQueue<Person> peopleQueue = new MyPriorityQueue<>(Comparator.comparingInt(p -> p.age)
);peopleQueue.add(new Person("Alice", 30));
peopleQueue.add(new Person("Bob", 25));
peopleQueue.add(new Person("Carol", 35));System.out.println(peopleQueue.poll()); // 输出 Bob(25)

如果你还有其他定制需求，比如：

支持删除任意元素
支持更新某个元素的优先级
支持构造函数初始化时传入一个集合

基于二叉堆实现的 PriorityQueue 因其高效的插入和删除最小（或最大）元素操作，在很多应用场景中都有着广泛的运用。下面我详细介绍几个常见的应用场景：

1. 图算法：路径搜索与最短路径

Dijkstra 算法

在 Dijkstra 算法中，优先队列用来维护从起点到各个节点的当前最短路径距离。每次从优先队列中选出距离最小的节点，然后根据这个节点更新其邻接点的距离。借助基于二叉堆的 PriorityQueue，其对插入和删除操作的平均时间复杂度为 O(log n)，使得算法在稀疏图中的效率大为提升。

A* 搜索算法

类似于 Dijkstra 算法，A* 算法也需要一个优先队列来维护待搜索节点，并根据预估函数 f(n)=g(n)+h(n) 的值来排列节点的优先级。使用二叉堆实现的 PriorityQueue 能够快速选取当前估值最低的节点，从而提高搜索效率。

2. 事件调度和仿真系统

离散事件模拟

在离散事件仿真系统中，每个事件都有一个触发时间，需要按照时间顺序执行。使用二叉堆实现的 PriorityQueue，可以将所有待执行事件按照时间顺序排列，每次只取最早触发的事件进行处理。这样的调度机制保证了事件的正确时序，适用于物流调度、网络仿真、制造系统仿真等场景。

操作系统任务调度

操作系统调度程序中也经常用到优先队列。比如在多任务系统中，任务可能具有不同的优先级或者截止时间。基于二叉堆的 PriorityQueue 可以迅速确定下一个需要处理的任务，有助于实现实时性要求较高的调度算法。

3. 排序和 Top-K 问题

堆排序

堆排序算法就是利用堆这种数据结构实现的排序算法。首先将数据构成一个堆，然后不断取出堆顶元素（最小/最大），并将剩余元素重新调整成堆结构。堆排序的时间复杂度为 O(n log n)，适合在部分特殊场景下使用。

查找 Top-K 元素

在海量数据中查找前 K 个最小或最大的元素，可以利用一个固定大小的 PriorityQueue。对每个新数据，和队列中的最值进行比较，若满足条件就进行替换操作，这样能够在 O(n log k) 的时间内找出前 K 个元素，非常适合实时数据处理与流式计算。

4. 网络和流量管理

网络路由与转发

在网络数据包调度和路由选择中，优先队列可以根据数据包的紧急程度、传输延迟等属性来决定数据包的传输顺序。使用基于二叉堆的实现，能够有效管理大量数据包，保证网络传输的高效和公平性。

服务质量（QoS）调控

在一些需要区分服务等级的场景（例如 VOIP、视频流处理等），采用 PriorityQueue 可以确保高优先级数据（如实时音视频数据）优先传输，从而改善用户体验。

5. 金融和交易系统

高频交易系统

金融领域中的高频交易系统通常需要实时处理大量订单，并保证订单按照某种优先级（如价格、时间等）进行匹配。PriorityQueue 能够高效维护待处理的订单列表，使得交易处理的响应时间尽可能低。

风险管理

在风险评估和管理场景中，不同投资组合或交易策略可能具有不同的风险度量值。利用 PriorityQueue，可以快速锁定风险较高的部分并及时采取措施，实现高效监控和决策。

总结

基于二叉堆实现的 PriorityQueue 以其简单、高效的特性，在图算法、事件调度、任务调度、排序以及网络、金融等众多领域都有重要应用。其对插入、删除操作时间复杂度为 O(log n) 的优势，使得在数据量较大、实时性要求较高的场景中表现优异。通过支持自定义比较器，PriorityQueue 更加灵活，可以方便地应用在各种复杂的业务场景中。

✅ 实现目标

🚀 实现代码（Java）

📦 示例用法

✅ 改造目标

🚀 改造后的 Java 实现：支持 Comparator 的 PriorityQueue

📦 示例用法

✅ 默认最小堆

✅ 最大堆（传入自定义 Comparator）

✅ 自定义对象排序（按年龄升序）

1. 图算法：路径搜索与最短路径

Dijkstra 算法

A* 搜索算法

2. 事件调度和仿真系统

离散事件模拟

操作系统任务调度

3. 排序和 Top-K 问题

堆排序

查找 Top-K 元素

4. 网络和流量管理

网络路由与转发

服务质量（QoS）调控

5. 金融和交易系统

高频交易系统

风险管理

总结

相关文章：