最近看了PriorityQueue的源码实现后，我深有感悟，其实本质上就是用了堆的数据结构，我也自己尝试实现了优先级队列的代码，不多说了，代码如下。
目录
源码实现
最近看了PriorityQueue的源码实现后，我深有感悟，其实本质上就是用了堆的数据结构，我也自己尝试实现了优先级队列的代码，不多说了，代码如下。
/**
* 自定义优先级队列实现，基于最小堆数据结构。
* 这个实现支持插入和删除操作，并且保证队列头部始终是最小的元素。
* 内部使用数组表示二叉堆，通过上浮和下沉操作维护堆的性质。
*/
public class CustomPriorityQueue<E> {
/**
* 默认初始容量，选择16是因为它是2的幂，便于扩容操作，
* 同时也是一个比较合理的初始值，可以避免过多的扩容
*/
private static final int DEFAULT_INITIAL_CAPACITY = 16;
/**
* 存储元素的数组，使用Object数组是因为要支持泛型，
* 实际使用时会进行类型转换
*/
private Object[] elements;
/**
* 当前队列中的元素数量，用于跟踪数组中实际存储的元素个数，
* 同时也用作下一个元素插入的位置索引
*/
private int size;
/**
* 比较器对象，用于确定元素之间的优先级顺序，
* 如果为null则使用元素的自然顺序
*/
private final Comparator<? super E> comparator;
/**
* 构造方法，创建一个使用自然顺序的优先级队列。
* 初始化数组大小为默认容量，不指定比较器。
*/
public CustomPriorityQueue() {
this(DEFAULT_INITIAL_CAPACITY, null);
}
/**
* 构造方法，创建一个使用指定比较器的优先级队列。
* 这个构造方法允许用户自定义元素的优先级规则。
*/
public CustomPriorityQueue(Comparator<? super E> comparator) {
this(DEFAULT_INITIAL_CAPACITY, comparator);
}
/**
* 构造方法，创建指定初始容量和比较器的优先级队列。
* 这是最完整的构造方法，其他构造方法都会调用这个方法。
*/
public CustomPriorityQueue(int initialCapacity, Comparator<? super E> comparator) {
if (initialCapacity < 1) {
throw new IllegalArgumentException("初始容量必须大于0");
}
this.elements = new Object[initialCapacity];
this.comparator = comparator;
}
/**
* 向队列中添加元素。首先将元素添加到数组末尾，然后通过上浮操作维护堆的性质。
* 如果数组空间不足，会触发扩容操作。这个方法的时间复杂度是O(log n)。
*/
public void offer(E e) {
if (e == null) {
throw new NullPointerException("不能插入null元素");
}
// 检查是否需要扩容
if (size >= elements.length) {
grow();
}
// 添加元素并上浮
elements[size] = e;
siftUp(size++);
}
/**
* 获取并移除队列头部的元素。这个元素是队列中最小的元素。
* 移除后，将最后一个元素移到头部，然后通过下沉操作维护堆的性质。
* 如果队列为空，返回null。这个方法的时间复杂度是O(log n)。
*/
public E poll() {
if (size == 0) {
return null;
}
// 获取并移除头部元素
E result = (E) elements[0];
elements[0] = elements[--size];
elements[size] = null;
if (size > 0) {
siftDown(0);
}
return result;
}
/**
* 查看队列头部元素但不移除。这个方法只是简单地返回数组第一个位置的元素，
* 不会修改队列的结构。如果队列为空，返回null。时间复杂度是O(1)。
*/
public E peek() {
return size == 0 ? null : (E) elements[0];
}
/**
* 上浮操作，用于在插入新元素后维护堆的性质。
* 将新插入的元素与其父节点比较，如果小于父节点则交换位置，
* 直到找到合适的位置或达到根节点。
*/
private void siftUp(int k) {
while (k > 0) {
int parent = (k - 1) >>> 1;
if (compare(k, parent) >= 0) {
break;
}
swap(k, parent);
k = parent;
}
}
/**
* 下沉操作，用于在移除元素后维护堆的性质。
* 将节点与其较小的子节点比较，如果大于子节点则交换位置，
* 直到找到合适的位置或达到叶子节点。
*/
private void siftDown(int k) {
int half = size >>> 1;
while (k < half) {
int child = (k << 1) + 1;
int right = child + 1;
if (right < size && compare(right, child) < 0) {
child = right;
}
if (compare(k, child) <= 0) {
break;
}
swap(k, child);
k = child;
}
}
/**
* 比较两个位置的元素。这个方法会根据构造时指定的比较器或元素的自然顺序
* 来比较元素。返回负数表示第一个元素较小，正数表示第一个元素较大。
*/
private int compare(int i, int j) {
E e1 = (E) elements[i];
E e2 = (E) elements[j];
return comparator != null ?
comparator.compare(e1, e2) :
((Comparable<? super E>)e1).compareTo(e2);
}
/**
* 交换数组中两个位置的元素。
* 这是一个简单的辅助方法，用于堆的调整过程中。
*/
private void swap(int i, int j) {
Object temp = elements[i];
elements[i] = elements[j];
elements[j] = temp;
}
/**
* 扩容操作，当数组空间不足时调用。
* 创建一个更大的数组（通常是原来的1.5倍），并将原有元素复制过去。
*/
private void grow() {
int oldCapacity = elements.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
elements = Arrays.copyOf(elements, newCapacity);
}
/**
* 返回队列中的元素个数。
* 这是一个O(1)的操作，因为我们维护了size字段。
*/
public int size() {
return size;
}
/**
* 检查队列是否为空。
* 同样是O(1)的操作，直接检查size字段即可。
*/
public boolean isEmpty() {
return size == 0;
}
}这个优先级队列的实现基于二叉堆数据结构，使用数组来存储堆元素。它支持插入（offer）和删除（poll）操作，这两个操作的时间复杂度都是O(log n)。查看队列头部元素（peek）的操作时间复杂度是O(1)。队列可以使用自定义的比较器来决定元素的优先级顺序，如果没有提供比较器，则使用元素的自然顺序。
这个实现包含了必要的数组扩容机制，扩容机制的选择用了ArrayList的1.5倍，当元素数量超过数组容量时，会创建一个更大的数组并复制元素。扩容策略是将数组大小增加50%，这是一个在时间和空间效率之间的平衡。
测试用例代码
public class PriorityQueueTest {
public static void main(String[] args) {
// 测试基本功能
testBasicOperations();
// 测试大量数据
testLargeDataset();
// 测试自定义比较器
testCustomComparator();
// 测试性能
testPerformance();
}
/**
* 测试基本的增删改查操作
*/
private static void testBasicOperations() {
System.out.println("=== 测试基本操作 ===");
CustomPriorityQueue<Integer> queue = new CustomPriorityQueue<>();
// 添加一些数字
queue.offer(5);
queue.offer(3);
queue.offer(7);
queue.offer(1);
queue.offer(9);
System.out.println("队列大小: " + queue.size());
// 依次取出元素，验证顺序
System.out.println("元素出队顺序：");
while (!queue.isEmpty()) {
System.out.print(queue.poll() + " ");
}
System.out.println("\n");
}
/**
* 测试大量数据的处理
*/
private static void testLargeDataset() {
System.out.println("=== 测试大量数据 ===");
CustomPriorityQueue<Integer> queue = new CustomPriorityQueue<>();
// 生成1000个随机数
Random random = new Random();
List<Integer> numbers = new ArrayList<>();
System.out.println("添加1000个随机数...");
for (int i = 0; i < 1000; i++) {
int num = random.nextInt(10000);
queue.offer(num);
numbers.add(num);
}
// 验证最小值
List<Integer> sortedNumbers = new ArrayList<>(numbers);
Collections.sort(sortedNumbers);
System.out.println("验证前10个最小值：");
for (int i = 0; i < 10; i++) {
int expected = sortedNumbers.get(i);
int actual = queue.poll();
System.out.printf("Expected: %d, Actual: %d, Correct: %b%n",
expected, actual, expected == actual);
}
System.out.println();
}
/**
* 测试自定义比较器（使用字符串长度作为优先级）
*/
private static void testCustomComparator() {
System.out.println("=== 测试自定义比较器 ===");
CustomPriorityQueue<String> queue = new CustomPriorityQueue<>(
(s1, s2) -> s1.length() - s2.length()
);
// 添加不同长度的字符串
String[] words = {
"pneumonoultramicroscopicsilicovolcanoconiosis", // 45字母
"supercalifragilisticexpialidocious", // 34字母
"incomprehensibilities", // 21字母
"international", // 13字母
"computer", // 8字母
"java", // 4字母
"hi" // 2字母
};
for (String word : words) {
queue.offer(word);
}
System.out.println("按长度从短到长输出：");
while (!queue.isEmpty()) {
String word = queue.poll();
System.out.printf("单词: %-45s 长度: %d%n", word, word.length());
}
System.out.println();
}
/**
* 测试性能和压力测试
*/
private static void testPerformance() {
System.out.println("=== 性能测试 ===");
CustomPriorityQueue<Integer> queue = new CustomPriorityQueue<>();
int testSize = 100000;
// 测试插入性能
long startTime = System.currentTimeMillis();
Random random = new Random();
for (int i = 0; i < testSize; i++) {
queue.offer(random.nextInt(1000000));
}
long insertTime = System.currentTimeMillis() - startTime;
System.out.printf("插入 %d 个元素耗时: %d ms%n", testSize, insertTime);
// 测试删除性能
startTime = System.currentTimeMillis();
int count = 0;
int previousValue = Integer.MIN_VALUE;
boolean isOrdered = true;
while (!queue.isEmpty()) {
int current = queue.poll();
if (current < previousValue) {
isOrdered = false;
break;
}
previousValue = current;
count++;
}
long removeTime = System.currentTimeMillis() - startTime;
System.out.printf("删除 %d 个元素耗时: %d ms%n", count, removeTime);
System.out.println("元素顺序正确: " + isOrdered);
// 测试极限情况
System.out.println("\n测试极限情况...");
queue = new CustomPriorityQueue<>();
// 添加一些特殊值
int[] specialValues = {
Integer.MAX_VALUE,
Integer.MIN_VALUE,
0,
-1,
1,
Integer.MAX_VALUE - 1,
Integer.MIN_VALUE + 1
};
for (int value : specialValues) {
queue.offer(value);
}
System.out.println("特殊值排序结果：");
while (!queue.isEmpty()) {
System.out.print(queue.poll() + " ");
}
System.out.println("\n");
// 测试重复值
System.out.println("测试重复值...");
queue = new CustomPriorityQueue<>();
for (int i = 0; i < 10; i++) {
queue.offer(5);
queue.offer(3);
queue.offer(7);
}
System.out.println("重复值排序结果：");
while (!queue.isEmpty()) {
System.out.print(queue.poll() + " ");
}
System.out.println("\n");
}
}测试结果如下
