-
public class PriorityQueue
基于优先级堆的无界优先级队列。优先级队列的元素根据它们的自然顺序进行排序，或者由队列构建时提供的 Comparator 排序，具体取决于使用的构造函数。优先级队列不允许空元素。依赖于自然排序的优先级队列也不允许插入不可比较的对象（这样做可能会导致 ClassCastException）。extends AbstractQueue implements Serializable 此队列的头相对于指定的排序是最小的元素。如果多个元素被绑定为最小值，头部是这些元素的一个，关系被任意地打破。队列检索操作poll，remove，peek，和element访问在队列的头元素。
一个优先队列是无界的，但有一个内部容量用于管理存储在队列中的元素的数组的大小。它总是至少和队列大小一样大。当元素被添加到优先级队列中时，它的容量会自动增长。未指定增长策略的细节。
这个类和它的迭代器实现所有的可选方法的Collection和Iterator接口。方法iterator()提供的迭代器不能保证遍历优先级队列的元素在任何特定的顺序。如果你需要有序遍历，考虑使用Arrays.sort(pq.toArray())。
请注意，此实现不同步。多线程不能访问PriorityQueue实例同时如果线程修改队列。相反，使用线程安全的java.util.concurrent.PriorityBlockingQueue。
注：该实现为入队和出队方法（offer、poll、remove() 和 add）提供了 O(log(n)) 时间； remove(Object) 和 contains(Object) 方法的线性时间；以及检索方法（peek、element 和 size）的恒定时间
//默认容量
private static final int DEFAULT_INITIAL_CAPACITY = 11;
//队列是通过数组来实现的
transient Object[] queue; // non-private to simplify nested class access
//队列中的元素值
private int size = 0;
// 队列中元素的比较方法
private final Comparator comparator;
//队列被修改操作的次数，请参考ArrayList中的modCount
transient int modCount = 0; // non-private to simplify nested class access
构造方法
// 指定初始容量和比较方法
public PriorityQueue(int initialCapacity,
Comparator 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;
}
//使用默认初始容量， 比较方法null
public PriorityQueue() {
this(DEFAULT_INITIAL_CAPACITY, null);
}
//指定初始容量， 比较方法为null
public PriorityQueue(int initialCapacity) {
this(initialCapacity, null);
}
//使用默认初始容量， 指定比较方法
public PriorityQueue(Comparator comparator) {
this(DEFAULT_INITIAL_CAPACITY, comparator);
}
//初始化的时候插入集合C的元素
public PriorityQueue(Collection c) {
if (c instanceof SortedSet) { //如果是SortedSet实例
SortedSet ss = (SortedSet) c;
//当前比较方法是c 的比较方法
this.comparator = (Comparator) ss.comparator();
// 初始化元素
initElementsFromCollection(ss);
}
else if (c instanceof PriorityQueue) { // 如果是PriorityQueue的实例
PriorityQueue pq = (PriorityQueue) c;
// 当前比较方法是c 的比较方法
this.comparator = (Comparator) pq.comparator();
// 初始化元素
initFromPriorityQueue(pq);
}
else {
this.comparator = null;
initFromCollection(c);
}
}
//初始化的时候插入PriorityQueue队列 C的元素
public PriorityQueue(PriorityQueue c) {
//当前比较方法使用当前 c的比较方法
this.comparator = (Comparator) c.comparator();
// 初始化元素
initFromPriorityQueue(c);
}
//初始化来自集合元素
private void initElementsFromCollection(Collection c) {
Object[] a = c.toArray();
if (c.getClass() != ArrayList.class)
//因为ArrayList的实现原理本身就是Object[]数组，所以不用Arrays.copyOf来生成一个Object[]数组
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) // 这里保证了PriorityQueue元素不能为空
throw new NullPointerException();
this.queue = a;
this.size = a.length;
}
private void initFromPriorityQueue(PriorityQueue c) {
if (c.getClass() == PriorityQueue.class) { //这里应该是为为了防止是PriorityQueue的 //子类
//如果当前C是PriorityQueue.class则可以直接定义
this.queue = c.toArray();
this.size = c.size();
} else {
initFromCollection(c);
}
}
private void initFromCollection(Collection c) {
initElementsFromCollection(c);
heapify();
}
private void heapify() {
for (int i = (size >>> 1) - 1; i >= 0; i--)
-- 这里是i的最大值取的是size/2 - 1 不明白为啥这样做，继续往下走
siftDown(i, (E) queue[i]);
}
private void siftDown(int k, E x) {
if (comparator != null) // 指定比较方法
siftDownUsingComparator(k, x);
else //默认比较方法
siftDownComparable(k, x);
}
private void siftDownUsingComparator(int k, E x) {
int half = size >>> 1; //这里取size的一半
//这里用k 0)
c = queue[child = right];
if (comparator.compare(x, (E) c) <= 0)
break;
queue[k] = c;
k = child;
}
queue[k] = x;
}
//看完这里如果你熟悉排序算法的话，这里用的是堆排序
private void siftDownComparable(int k, E x) {
Comparable key = (Comparable)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) 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;
}
从上面的构造方法可以看出， 队列是通过数组来存储元素的，然后可以指定排序。
使用的堆排序算法对其内部的元素进行的排序，相要理解堆排序的同学，请看下面这篇文档
算法导论学习笔记 第6章 堆排序_GUANGZHAN的专栏-CSDN博客
public boolean add(E e) {
return offer(e);
}
调用了offer
offer 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) //如果i==0说明队列是空的，所以queue[0] 直接是当前元素
queue[0] = e;
else
siftUp(i, e);
return true;
}
//扩容
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) //这里是为了防止扩容后的容量超出 int 的最大值
newCapacity = hugeCapacity(minCapacity);
queue = Arrays.copyOf(queue, newCapacity); //熟悉的复制
}
private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x);
}
@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;
}
@SuppressWarnings("unchecked") //默认比较方法的堆排序算法
private void siftUpComparable(int k, E x) {
Comparable key = (Comparable) 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;
}
通过构造方法和添加offer可以确定，队列中最小的元素是排在第一位的
removepublic boolean remove(Object o) {
int i = indexOf(o);
if (i == -1)
return false;
else {
removeAt(i);
return true;
}
}
boolean removeEq(Object o) {
for (int i = 0; i < size; i++) {
if (o == queue[i]) {
removeAt(i);
return true;
}
}
return false;
}
@SuppressWarnings("unchecked")
private E removeAt(int i) {
// assert i >= 0 && i < size;
modCount++;
int s = --size;
if (s == i) // removed last element // 移除最后的元素，不用操作排序
queue[i] = null;
else {
E moved = (E) queue[s];
queue[s] = null; // 将数组的最后一个元素设为空
siftDown(i, moved); //通过siftDown来调整最后一个元素的位置，大致原理就是将最后一 //个元素替换i位置的元素，然后堆排序
if (queue[i] == moved) {
siftUp(i, moved);
if (queue[i] != moved)
return moved;
}
}
return null;
}
poll
//返回并移除首位
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); //堆排序， 原理参考remove
return result;
}
peek
public E peek() {
return (size == 0) ? null : (E) queue[0];
}
element
//AbstractQueue的element
public E element() {
E x = peek(); //这里使用的是PriorityQueue的peek()
if (x != null)
return x;
else
throw new NoSuchElementException();
}
结论
结合类的描述：
1. PriorityQueue 是一个优先级队列， 可以指定元素的比较方法comparator
2. PriorityQueue是通过Objects数组来存储元素的，他最大存储Integer.MAX_VALUE个元素
3. PriorityQueue是通过堆排序算法进行排序的，元素的首位永远是最小的元素
4. 单向队列
6 不是线程安全的
上一章
