解析Java中PriorityQueue优先级队列结构的源码及用法

什么是优先级队列？

优先级队列是一种特殊的队列，它会根据元素的优先级来决定队列中元素的顺序。在Java中，我们可以使用PriorityQueue类来实现优先级队列。

PriorityQueue源码解析

Java中的优先级队列主要由以下几个部分组成：

PriorityQueue的构造函数

public PriorityQueue(int initialCapacity, Comparator<? super E> comparator) {
    if (initialCapacity < 1)
        throw new IllegalArgumentException();
    this.queue = new Object[initialCapacity];
    this.size = 0;
    this.comparator = comparator;
}

可以看到，PriorityQueue有一个构造函数，它接收两个参数：initialCapacity和comparator。initialCapacity表示优先级队列的初始容量，而comparator则用来比较队列中的元素。

add和offer方法

public boolean add(E e) {
    return offer(e);
}

public boolean offer(E e) {
    if (e == null)
        throw new NullPointerException();
    modCount++;
    int i = size;
    if (i >= queue.length)
        grow(i + 1);
    size = i + 1;
    if (i == 0)
        queue[0] = e;
    else
        siftUp(i, e);
    return true;
}

add和offer方法都可以添加元素到优先级队列中。其中，offer方法返回一个布尔值，表示元素是否被成功添加到队列中。

remove和poll方法

public boolean remove(Object o) {
    int index = indexOf(o);
    if (index == -1)
        return false;
    else {
        removeAt(index);
        return true;
    }
}

public E poll() {
    if (size == 0)
        return null;
    int s = --size;
    modCount++;
    E result = (E) queue[0];
    E x = (E) queue[s];
    queue[s] = null;
    if (s != 0)
        siftDown(0, x);
    return result;
}

remove和poll方法都可以从优先级队列中移除元素。其中，poll方法会返回队列中的第一个元素，并将其从队列中移除。

其他方法

PriorityQueue中还包含了多个其他方法，比如peek、element、size等等。这些方法都可以用来操作优先级队列中的元素。

使用PriorityQueue

下面，我们来看两个优先级队列的使用示例。

示例1：使用默认排序方式

PriorityQueue<Integer> queue = new PriorityQueue<>();
queue.offer(3);
queue.offer(1);
queue.offer(4);
queue.offer(2);
System.out.println(queue.poll()); // 输出1
System.out.println(queue.poll()); // 输出2

以上示例中，我们使用默认的比较方式，即从小到大排序。

示例2：使用自定义比较器进行排序

PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2 - o1);
queue.offer(3);
queue.offer(1);
queue.offer(4);
queue.offer(2);
System.out.println(queue.poll()); // 输出4
System.out.println(queue.poll()); // 输出3

以上示例中，我们创建了一个自定义的比较器，使队列从大到小排序。

总结

本篇攻略中，我们详细讲解了Java中PriorityQueue优先级队列的源码及用法。通过本篇文章的学习，读者应该已经掌握了PriorityQueue的常见使用方式，以及如何利用自定义比较器来对队列中的元素进行排序。