⚾ PriorityQueue
2022年6月9日
- Java
⚾ PriorityQueue
1. 类注释
- 复杂度
- O(log N):
offer&poll&remove()&add - O(N) :
remove(Object)&contains(Object) - O(1) :
peek&element&size
- 非线程安全
2. 类图
public class PriorityQueue<E> extends AbstractQueue<E> implements java.io.Serializable {
// ......
}
3. 属性
private static final long serialVersionUID = -7720805057305804111L;
private static final int DEFAULT_INITIAL_CAPACITY = 11;
/**
* 平衡二叉堆
* queue[n] 父节点的左右子节点分别为 queue[2 * n + 1] & queue[2 * n + 2]
* 默认小根堆，根据自然顺序排列
*/
transient Object[] queue; // non-private to simplify nested class access
private int size = 0; // 优先级队列中的元素数。
private final Comparator<? super E> comparator; // 比较器，如果优先级队列使用元素的自然顺序，则为 null。
/**
* 此优先级队列被 结构修改 的次数。
*/
transient int modCount = 0; // 非私有以简化嵌套类访问
/**
* 数组最大长度
* 减去对象头 [8字节] 的长度
* 有些 JVM 还会给数组留出一定长度，因此可能造成 OOM
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
4. 构造函数
/**
* 无参构造函数，初始容量 = 11 & 默认排序
*/
public PriorityQueue() {
this(DEFAULT_INITIAL_CAPACITY, null);
}
/**
* 指定容量大小 & 默认排序
*
* @param initialCapacity 此优先级队列的初始容量
* @throws IllegalArgumentException if {@code initialCapacity} is less
* than 1
*/
public PriorityQueue(int initialCapacity) {
this(initialCapacity, null);
}
/**
* 初始容量 = 11 & 指定排序方式
*
* @param comparator 将用于排序此优先级队列的比较器。如果 {@code null}，将使用元素的 {@linkplain Comparable 自然排序}。
* @since 1.8
*/
public PriorityQueue(Comparator<? super E> comparator) {
this(DEFAULT_INITIAL_CAPACITY, comparator);
}
/**
* 指定容量大小 & 指定排序方式
*
* @param initialCapacity 此优先级队列的初始容量
* @param comparator 将用于排序此优先级队列的比较器。如果 {@code null}，将使用元素的 {@linkplain Comparable 自然排序}。
* @throws IllegalArgumentException if {@code initialCapacity} is
* less than 1
*/
public PriorityQueue(int initialCapacity, Comparator<? super E> comparator) {
if (initialCapacity < 1)
throw new IllegalArgumentException();
this.queue = new Object[initialCapacity];
this.comparator = comparator;
}
/**
* 根据给定集合建堆
*
* @param c the collection whose elements are to be placed
* into this priority queue
* @throws ClassCastException if elements of the specified collection
* cannot be compared to one another according to the priority
* queue's ordering
* @throws NullPointerException if the specified collection or any
* of its elements are null
*/
@SuppressWarnings("unchecked")
public PriorityQueue(Collection<? extends E> c) {
if (c instanceof SortedSet<?>) {
// 若为 有序集合，继承原有 排序规则，数组元素顺序不变
SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
this.comparator = (Comparator<? super E>) ss.comparator();
initElementsFromCollection(ss);
}
else if (c instanceof PriorityQueue<?>) {
// 若本身为 PQ，继承原有 排序规则
PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
this.comparator = (Comparator<? super E>) pq.comparator(); // 继承原有排序规则
initFromPriorityQueue(pq);
}
else {
// 若为 普通集合，排序规则为自然升序，重建堆
this.comparator = null;
initFromCollection(c);
}
}
// 有序集合 的元素初始化 - 直接将数组元素一对一转移到 PQ 数组中
private void initElementsFromCollection(Collection<? extends E> c) {
Object[] a = c.toArray();
// If c.toArray incorrectly doesn't return Object[], copy it.
if (a.getClass() != Object[].class)
a = Arrays.copyOf(a, a.length, Object[].class);
int len = a.length;
if (len == 1 || this.comparator != null)
for (int i = 0; i < len; i++)
if (a[i] == null)
throw new NullPointerException(); // 说明 PQ 内的元素不能为 null
this.queue = a; // 直接赋值给初始数组，并没有按照排序器的规则依次添加
this.size = a.length;
}
// 优先队列 的元素初始化
private void initFromPriorityQueue(PriorityQueue<? extends E> c) {
if (c.getClass() == PriorityQueue.class) {
this.queue = c.toArray(); // 数组元素原有顺序不变
this.size = c.size();
} else {
initFromCollection(c);
}
}
/**
* 普通集合 的元素初始化 - 需要重建堆保证数组元素初始顺序的准确性
*
* @param c the collection
*/
private void initFromCollection(Collection<? extends E> c) {
initElementsFromCollection(c); // 复制元素到 PQ 数组
heapify(); // 重建堆
}
/**
* 这里重建堆，不是从 边界开始依次添加，而是从中点开始，往左边尝试堆的下沉来建堆
*
* 疑问？
* 理论上，如果根据我自己写的话，应该是遍历下标，将当前下标元素通过 siftUp 上浮插入到前面已经建好的堆中
* 而源码这里，只遍历了前半部分，且用的是 siftDown 函数
*/
@SuppressWarnings("unchecked")
private void heapify() {
for (int i = (size >>> 1) - 1; i >= 0; i--)
siftDown(i, (E) queue[i]);
}
/**
* Creates a {@code PriorityQueue} containing the elements in the
* specified priority queue. This priority queue will be
* ordered according to the same ordering as the given priority
* queue.
*
* @param c the priority queue whose elements are to be placed
* into this priority queue
* @throws ClassCastException if elements of {@code c} cannot be
* compared to one another according to {@code c}'s
* ordering
* @throws NullPointerException if the specified priority queue or any
* of its elements are null
*/
@SuppressWarnings("unchecked")
public PriorityQueue(PriorityQueue<? extends E> c) {
this.comparator = (Comparator<? super E>) c.comparator();
initFromPriorityQueue(c);
}
/**
* Creates a {@code PriorityQueue} containing the elements in the
* specified sorted set. This priority queue will be ordered
* according to the same ordering as the given sorted set.
*
* @param c the sorted set whose elements are to be placed
* into this priority queue
* @throws ClassCastException if elements of the specified sorted
* set cannot be compared to one another according to the
* sorted set's ordering
* @throws NullPointerException if the specified sorted set or any
* of its elements are null
*/
@SuppressWarnings("unchecked")
public PriorityQueue(SortedSet<? extends E> c) {
this.comparator = (Comparator<? super E>) c.comparator();
initElementsFromCollection(c);
}
5. 常见方法
1) 插入元素
/**
* 插入元素
*
* @return {@code true} (as specified by {@link Collection#add})
* @throws ClassCastException 如果指定的元素不能根据优先级队列的顺序与当前在此优先级队列中的元素进行比较
* @throws NullPointerException if the specified element is null
*/
public boolean add(E e) {
return offer(e);
}
/**
* 插入元素，非空
*
* @return {@code true} (as specified by {@link Queue#offer})
* @throws ClassCastException if the specified element cannot be
* compared with elements currently in this priority queue
* according to the priority queue's ordering
* @throws NullPointerException if the specified element is null
*/
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;
}
/**
* 扩容
*
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
int oldCapacity = queue.length;
// oldCapacity < 64 => 2 * n + 2
// 否则 => 1.5 * n
int newCapacity = oldCapacity + ((oldCapacity < 64) ?
(oldCapacity + 2) :
(oldCapacity >> 1));
// overflow-conscious code
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
queue = Arrays.copyOf(queue, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
/**
* 在下标 k 处插入 x，插入后需维护堆的平衡
*
* 简化和加速强制和比较。 Comparable 和 Comparator 版本被分成不同的方法，这些方法在其他方面是相同的。 （对于 siftDown 也是如此。）
*
* @param k 要填补的位置
* @param x 要插入的元素
*/
private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x);
}
/*
* 自然排序规则下的 元素上浮
* 需要和 parent 比较，如果比 parent 小，那么需要上浮
* 将父子调换，自己由子变父，继续判断是否上浮
*/
@SuppressWarnings("unchecked")
private void siftUpComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>) x;
while (k > 0) {
// 假设 parent 的下标为 x，则 左孩子为 2x + 1，右孩子为 2x + 2
// 反之，若某节点下标为 y，则 parent 必为 (x - 1) >>> 1
int parent = (k - 1) >>> 1;
Object e = queue[parent]; // 父节点的值
if (key.compareTo((E) e) >= 0)
break;
queue[k] = e; // 父子关系颠倒
k = parent;
}
queue[k] = key; // 找到自己应该处于的位置，填充值
}
@SuppressWarnings("unchecked")
private void siftUpUsingComparator(int k, E x) {
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = queue[parent];
if (comparator.compare(x, (E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = x;
}
2) 删除元素
/**
* 删除某个元素，若存在，则返回 true；否则返回 false
*
* @param o element to be removed from this queue, if present
* @return {@code true} if this queue changed as a result of the call
*/
public boolean remove(Object o) {
int i = indexOf(o); // 获取元素所在下标
if (i == -1)
return false;
else {
removeAt(i); // 删除指定下标元素
return true;
}
}
private int indexOf(Object o) {
if (o != null) {
for (int i = 0; i < size; i++)
if (o.equals(queue[i]))
return i;
}
return -1;
}
/**
* 删除指定下标的元素，为 私有 方法
*/
@SuppressWarnings("unchecked")
private E removeAt(int i) {
modCount++;
size --;
int s = size;
if (s == i) // 删除的正好是最后一个元素
queue[i] = null; // 可以看出，这里并没有回收最后一个下标处的数组空间，这样后续添加一个元素时，无需扩容，可以直接使用该下标空间
else {
E moved = (E) queue[s]; // 获取最后一个元素
queue[s] = null; // 最后一个元素下标处 = null
siftDown(i, moved); // 在下标 i 处放入 最后一个元素的值，这样就相当于本来下标 i 处的值被覆盖了，重新维护堆的平衡
if (queue[i] == moved) { // 说明最后一个元素放在删除下标处下沉不了
siftUp(i, moved); // 尝试能否 上浮
if (queue[i] != moved)
return moved; // 说明上浮成功
}
}
return null;
}
/**
* 想要在下标 k 处插入元素 x，插入后仍需要保证堆的平衡
*
* @param k the position to fill
* @param x the item to insert
*/
private void siftDown(int k, E x) {
if (comparator != null)
siftDownUsingComparator(k, x);
else
siftDownComparable(k, x);
}
/*
* 由于下标 i 处想要插入的值 x 可能比左右孩子小，因此需要进行 下沉 判断
*/
@SuppressWarnings("unchecked")
private void siftDownComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>)x;
int half = size >>> 1; // loop while a non-leaf
while (k < half) {
// 找到左右孩子的最小那个
int child = (k << 1) + 1; // 假设左孩子为 左右孩子的最小
Object c = queue[child];
int right = child + 1;
if (right < size &&
((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
c = queue[child = right];
if (key.compareTo((E) c) <= 0)
break;
queue[k] = c; // 父比孩子大，需要下沉，父子关系颠倒
k = child;
}
queue[k] = key;
}
@SuppressWarnings("unchecked")
private void siftDownUsingComparator(int k, E x) {
int half = size >>> 1;
while (k < half) {
int child = (k << 1) + 1;
Object c = queue[child];
int right = child + 1;
if (right < size &&
comparator.compare((E) c, (E) queue[right]) > 0)
c = queue[child = right];
if (comparator.compare(x, (E) c) <= 0)
break;
queue[k] = c;
k = child;
}
queue[k] = x;
}
// 删除 堆顶元素
@SuppressWarnings("unchecked")
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); // 将最后一位元素移到堆顶元素，即 下标 0 处，下沉判断 - 重新维护堆的平衡
return result;
}
3) 查找元素
/**
* 判断是否存在某个元素
* More formally, returns {@code true} if and only if this queue contains
* at least one element {@code e} such that {@code o.equals(e)}.
*
* @param o object to be checked for containment in this queue
* @return {@code true} if this queue contains the specified element
*/
public boolean contains(Object o) {
return indexOf(o) != -1;
}
// 获取 堆顶元素
@SuppressWarnings("unchecked")
public E peek() {
return (size == 0) ? null : (E) queue[0];
}