PriorityQueue
PriorityQueue底层使用的是最小堆
重要属性
private final Comparator<? super E> comparator;
private static final int DEFAULT_INITIAL_CAPACITY = 11;
transient Object[] queue; // non-private to simplify nested class access
private int size = 0;
构造函数
构造函数使用的参数主要有两个:初始容量和排序规则
public PriorityQueue(int initialCapacity,
Comparator<? super E> comparator) {
// Note: This restriction of at least one is not actually needed,
// but continues for 1.5 compatibility
if (initialCapacity < 1)
throw new IllegalArgumentException();
this.queue = new Object[initialCapacity];
this.comparator = comparator;
}
add
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;
}
下面看一下堆中调整方法siftUp
private void siftUp(int k, E x) {
// 根据是否使用比较器,执行不同的方法,流程差不多
if (comparator != null)
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x);
}
private void siftUpComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>) x;
while (k > 0) {
// 获取当前节点的父节点
int parent = (k - 1) >>> 1;
Object e = queue[parent];
// 如果当前节点比父节点大,那么不用再向上调整了
// 找到插入位置了
if (key.compareTo((E) e) >= 0)
break;
// 否则需要交换孩子节点和父节点
queue[k] = e;
k = parent;
}
queue[k] = key;
}
```
## 扩容
```java
private void grow(int minCapacity) {
int oldCapacity = queue.length;
// Double size if small; else grow by 50%
// 如果当前容量小于64,那么容量加倍,否则容量增加一半
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);
}
```
## poll
不能直接通过迭代器访问队列的元素,因为迭代器将会顺序遍历底层数组,而该数组中的元素并不是有序的
```java
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;
}
```
```java
private void siftDown(int k, E x) {
if (comparator != null)
siftDownUsingComparator(k, x);
else
siftDownComparable(k, x);
}
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; // assume left child is least
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;
}
```