Java集合(一) —— Collection源码分析
Java集合(二) —— ArrayList源码分析
Java集合(三) —— LinkedList源码分析
Java集合(四) —— PriorityQueue源码分析
Java集合(五) —— HashSet源码分析
Java集合(六) —— LinkedHashSet源码分析
Java集合(七) —— TreeSet源码分析
Java集合(八) —— HashMap源码分析
Java集合(九) —— LinkedHashMap源码分析
Java集合(十) —— TreeMap源码分析
1.PriorityQueue继承关系图
PriorityQueue.png
2数据结构
// 数组
transient Object[] queue;
1.优先队列并不是按照FIFO进行数据操作的，其数据具有优先级，优先级高的元素先出队。优先队列是基于小顶堆(堆排序的一种)原理实现的。
2.堆：堆是一个树型结构，是一棵完全二叉树。完全二叉树是一层一层按照进入的顺序排列的。按照这个特性可以使用数组按照完全二叉树实现堆。
1469176-20190329000534658-1905270280.png
3.堆排序：利用堆这种数据结构所设计的一种排序算法。
- 大顶堆：根节点的值最大。子节点一定小于或等于父节点。
- 小顶堆：根节点的值最小。子节点一定大于或等于父节点。(Java中的优先队列(PriorityQueue)是基于小顶堆实现的。)
4.堆排序思想：
- 构建初始堆，将待排序序列构成一个大顶堆或小顶堆。
- 将堆顶元素与堆尾元素交换，并断开(从待排序列中移除)堆尾元素。
- 重复构建堆。
- 重复2~3，直到待排序列只剩一个元素(堆顶元素)。
3.性能分析
优先队列初始化堆时，其时间复杂度为O(n)；（怎样才是一个初始化好的堆？要求子节点不大于/不小于父节点，但是不要求是完全排好序的）
入队和出队时只是调整堆结构，并不需要将所有元素排序，其时间复杂度为O(log2n)（具体计算另行百度）。
4.源码分析
1.成员变量
// 数组默认容量
private static final int DEFAULT_INITIAL_CAPACITY = 11;
// 数据结构为数组
transient Object[] queue;
// 数组大小
private int size = 0;
// 比较器
private final Comparator<super E> comparator;
// 修改次数
transient int modCount = 0;
2.构造方法
public PriorityQueue() {
this(DEFAULT_INITIAL_CAPACITY, null);
}
// 指定初始容量
public PriorityQueue(int initialCapacity) {
this(initialCapacity, null);
}
// 指定比较器
public PriorityQueue(Comparator<super E> comparator) {
this(DEFAULT_INITIAL_CAPACITY, comparator);
}
// 指定初始容量和比较器
public PriorityQueue(int initialCapacity,
Comparator<super E> comparator) {
if (initialCapacity < 1)
throw new IllegalArgumentException();
this.queue = new Object[initialCapacity];
this.comparator = comparator;
}
// 使用集合构建优先队列
@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<?>) {
PriorityQueue<extends E> pq = (PriorityQueue<extends E>) c;
this.comparator = (Comparator<super E>) pq.comparator();
initFromPriorityQueue(pq);
}
else {
this.comparator = null;
initFromCollection(c);
}
}
@SuppressWarnings("unchecked")
public PriorityQueue(PriorityQueue<extends E> c) {
this.comparator = (Comparator<super E>) c.comparator();
initFromPriorityQueue(c);
}
@SuppressWarnings("unchecked")
public PriorityQueue(SortedSet<extends E> c) {
this.comparator = (Comparator<super E>) c.comparator();
initElementsFromCollection(c);
}
3.常用方法
- 新增元素
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;
}
private void siftUp(int k, E x) {
if (comparator != null)
// 使用自定义的比较器调整队列
siftUpUsingComparator(k, x);
else
// 使用默认的比较方法调整队列
siftUpComparable(k, x);
}
@SuppressWarnings("unchecked")
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;
}
@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;
}
关于扩容
private void grow(int minCapacity) {
int oldCapacity = queue.length;
// 扩容机制，容量小于64时，新容量 = 旧容量*2+2；大于64时，新容量 = 旧容量 + 旧容量 >> 1
int newCapacity = oldCapacity + ((oldCapacity < 64) ?
(oldCapacity + 2) :
(oldCapacity >> 1));
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 数组复制
queue = Arrays.copyOf(queue, newCapacity);
}
2.移除队列头元素
/**
* 移除队列头元素，内部调用了poll方法，如果队列为空则抛出异常
*/
public E remove() {
E x = poll();
if (x != null)
return x;
else
throw new NoSuchElementException();
}
/**
* 移除队列头元素，如果队列为空，则返回null
*/
@SuppressWarnings("unchecked")
public E poll() {
if (size == 0)
return null;
// 数组大小-1
int s = --size;
modCount++;
// 获取队列第一个元素
E result = (E) queue[0];
// 获取队列最后一个元素
E x = (E) queue[s];
// 将数组最后一个元素置为null
queue[s] = null;
if (s != 0)
// 调整堆结构
siftDown(0, x);
return result;
}
/**
* 调整堆，使最小元素位于堆顶
*/
private void siftDown(int k, E x) {
if (comparator != null)
// 使用指定的比较器
siftDownUsingComparator(k, x);
else
siftDownComparable(k, 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;
}
3.获取队列头元素
/**
* 获取队列头元素，内部调用了peek方法，如果队列为空则抛出异常
*/
public E element() {
E x = peek();
if (x != null)
return x;
else
throw new NoSuchElementException();
}
/**
* 获取队列头元素，如果队列为空则返回null
*/
public E peek() {
return (size == 0) null : (E) queue[0];
}
5.总结
- PriorityQueue优先队列，不适合一些经常出队入队的场景，但是他的优先级特性非常适合一些对顺序有要求的数据处理场景。
- 堆（完全二叉树）的数据结构不难理解，但是在优先队列中，出队和入队都可能引起堆结构的调整(实际上就是数组元素位置的调整)，调整算法有点晦涩难懂，有兴趣的朋友可以好好了解该算法的实现。
- 优先队列在工作中的场景比较有限（至少我工作中没有使用过），不喜欢的可以略过。