PriorityQueue集合源码分析
文章目录
- PriorityQueue集合源码分析
- 前置知识
- 一、字段分析
- 二、构造函数分析
- 三、方法分析
- 四、总结
- PriorityQueue 优先级队列，是基于堆的结构来构建的。而堆是基于完全二叉树来实现的，而二叉树除了可以用节点来实现也可以用数组实现（就是将二叉树按照层序便利，填充到数组中，父节点i，那么左子节点为2*i +1, 右子节点为 2 * i + 2，i 指数组索引），而PriorityQueue就是基于用数组实现的完全二叉树来实现的堆。
- PriorityQueue 默认是小顶堆。
前置知识
- 堆是一棵完全二叉树。
- 节点总数为n，那么非叶子节点数为 n/2，叶子节点数为 （n + 1）/ 2。
- 堆中的任意一个非叶子节点的值，总是不大于（小顶堆）或不小于（大顶堆）任意儿子节点的值。
- 堆中每个子树也可看做成一个堆。
- 更多堆的基础知识可查看这篇介绍：堆介绍
- 熟悉堆的性质与操作后，学习 PriorityQueue就很简单了。
- 这里简单实现下大顶堆
package com.example.demo.heap;
import java.util.Comparator;
/**
* 大顶堆的简单实现
*
* @param <E>
*/
public class BinaryHeap<E> implements Heap<E> {
private E[] elements;
private int size;
private Comparator<E> comparator;
private static final int DEFAULT_CAPACITY = 10;
public BinaryHeap(Comparator<E> comparator){
this.comparator = comparator;
this.elements = (E[]) new Object[DEFAULT_CAPACITY];
}
public BinaryHeap(){
this(null);
}
private int compare(E e1, E e2){
return comparator != null? comparator.compare(e1,e2): ((Comparable<E> )e1).compareTo(e2);
}
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public void clear() {
for (int i = 0; i < size; i++) {
elements[i] = null;
}
size = 0;
}
@Override
public void add(E element) {
//检查扩容(略)
//将元素添加到数组末尾
elements[size ++] = element;
//调整新添加元素子在堆中的位置(上浮）
siftUp(size - 1);
}
/**
* 从 index 位置开始进行上滤操作,其实就是不停的和父节点比较和调整，找到属于自己的位置
*/
private void siftUp(int index){
E e = elements[index];
while (index > 0){
//父节点
int pi = (index - 1) >> 1;
E pv = elements[pi];
if (compare(e,pv) <= 0) return;
swap(index,pi);
index = pi;
}
}
private void swap(int a, int b){
E temp = elements[a];
elements[a] = elements[b];
elements[b] = temp;
//拓展下，数据交换(数字类型)也可以用位运算代替
// elements[a] ^= elements[b];
// elements[b] ^= elements[a];
// elements[a] ^= elements[b];
}
//获取堆顶元素
@Override
public E get() {
emptyCheck();
return elements[0];
}
//删除堆顶元素。 交换删除 + 下浮
@Override
public E remove() {
emptyCheck();
E e = elements[0];
swap(0, -- size);
elements[size] = null;
//下浮
siftDown(0);
return e;
}
// 下浮
public void siftDown(int index){
E e = elements[index];
//完全二叉树的非叶子节点数量 公式 n = size / 2
int half = size >> 1;
while (index < half){
//和左右子节点中最大的节点进行交换
int left = (index << 1) + 1;
E leftVal = elements[left];
//判断有无右子节点
int right = left + 1;
if (right < size && compare(elements[right],leftVal) > 0){
left = right;
leftVal = elements[right];
}
//判断当前节点和子节点是否需要交换
if (compare(e, leftVal) < 0) break;
//交换
elements[index] = leftVal;
index = left;
}
//找到了合适的位置了
elements[index] = e;
}
@Override
public E replace(E element) {
elementNotNullCheck(element);
E remove = null;
if (size == 0){
elements[0] = element;
size ++;
}else {
remove = elements[0];
elements[0] = element;
siftDown(0);
}
siftDown(0);
return remove;
}
/**
* 批量建堆： 直接给一对无规律的数据建堆
* 方法一: 自上而下的上浮（相对较慢，每个节点都要进行上浮）
* 方法二：自下而上的下浮（更快，因为叶子节点无需下浮，可直接跳过）,我们采用此方法
*/
public void heapify(){
// //自上而下的上滤
// for (int i = 1; i < size; i++) {
// siftUp(i);
// }
//自上而下的下虑
for (int i = (size >> 1) - 1; i >= 0; i -- ) {
siftDown(i);
}
}
private void emptyCheck(){
if (size == 0)
throw new IndexOutOfBoundsException("Heap is Empty");
}
private void elementNotNullCheck(E element){
if (element == null)
throw new IllegalArgumentException("element must not be null");
}
}
一、字段分析
//默认的初始容量，即 数组的length
private static final int DEFAULT_INITIAL_CAPACITY = 11;
//用来存储数据的数组，PriorityQueue 是基于数组实现的堆。
transient Object[] queue;
//存储的数据个数
private int size = 0;
//比较器。每一个存储的元素必须是可比较的，具体体现是数据类型一定是实现了Comparator接口，
//或构建PririotyQueue 时传入自定义的Comparator比较器，否则会报错。如果两者都有，以你传入的为准。
private final Comparator<? super E> comparator;
//版本号，在迭代的过程中检测 PriorityQueue是否被修改。
transient int modCount = 0;
二、构造函数分析
//无参构造函数
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) {
// Note: This restriction of at least one is not actually needed,
// but continues for 1.5 compatibility
//给定容量不能小于1，否则报错
if (initialCapacity < 1)
throw new IllegalArgumentException();
//使用该容量创建数组
this.queue = new Object[initialCapacity];
//比较器赋值
this.comparator = comparator;
}
//使用 集合c 来创建，其实就是批量建堆
public PriorityQueue(Collection<? extends E> c) {
//如果集合c是有序集合，有序集合里必然有比较器
if (c instanceof SortedSet<?>) {
//将集合c向上转换
SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
//获取该集合的比较器，并赋给PriorityQueue
this.comparator = (Comparator<? super E>) ss.comparator();
//构建堆，因为当前c也是有序的，如果升序，就是小顶堆，如果降序，就是大顶堆
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);
}
}
//使用有序的集合c来构建堆，该方法构建完成后不能完全保证有序性，即PriorityQueue的性质
private void initElementsFromCollection(Collection<? extends E> c) {
//将集合c转化为数组
Object[] a = c.toArray();
// If c.toArray incorrectly doesn't return Object[], copy it.
//比如List<String> toArray() 就是 String[]了， 这步是为了去泛化
if (a.getClass() != Object[].class)
//进行浅拷贝
a = Arrays.copyOf(a, a.length, Object[].class);
//获取数组长度，用于遍历元素
int len = a.length;
//这段代码咋一看应该是保证集合c中不能有null。首先PriorityQueue中的元素确实不能有null，比如添加元素时，直接判断元素时null抛出异常
//但是这段代码只能保证部分情况下不能有null，还需要其他的方法配合才可以。
//1.如果 集合 c 是 属于 SortedSet 子类，并且没有自定义比较器，c本身就不会支持 null，也不会走到当前方法，可是
//如果当时传入了比较器，对null进行了处理，那么对于c来说是可以支持null了，那么可以到当前这个，就会出发for循环，不允许你这种情况。
//2。如果 集合c 本身就是 PriorityQueue，那么这里可定不会触发，但如果你自定义了PriorityQueue子类，子类中允许添加null，那么这
//的for循环不会触发，但是在进行堆化操作时报错，从而达到不允许此类情况
//3。如果你是属于其他情况，比如List 集合，ok，这里也不会触发for循环，没关系，堆化操作会卡住你。
//总而言之：PriorityQueue 不支持元素中出现null。自定一比较器去处理也不行！！（向TreeSet默认不支持null排序，
//但是自定义比较器处理掉null情况就不会有问题，这点他们有区别）。而这段代码可以卡住部分集合c有null的情况（不是全部，比如list添加两个null）。
if (len == 1 || this.comparator != null)
for (int i = 0; i < len; i++)
if (a[i] == null)
throw new NullPointerException();
//-------------------------------------
//赋值给PriorityQueue存储元素的数组
this.queue = a;
//更新数据个数
this.size = a.length;
}
//使用 PriorityQueue 或其子类来构建
public PriorityQueue(PriorityQueue<? extends E> c) {
//使用传入c的比较器
this.comparator = (Comparator<? super E>) c.comparator();
initFromPriorityQueue(c);
}
//使用 PriorityQueue 或其子类来构建
private void initFromPriorityQueue(PriorityQueue<? extends E> c) {
//c 确实是 PriorityQueue 本身，那不会有问题，直接赋值即可。
if (c.getClass() == PriorityQueue.class) {
this.queue = c.toArray();
this.size = c.size();
} else {
//是PriorityQueue子类，那可能存在问题了，要进行堆化操作，并检查元素中是否有null
initFromCollection(c);
}
}
private void initFromCollection(Collection<? extends E> c) {
//将集合c给当前队列，执行完后可能是无序的
initElementsFromCollection(c);
//进行堆化操作，堆排序
heapify();
}
public PriorityQueue(SortedSet<? extends E> c) {
this.comparator = (Comparator<? super E>) c.comparator();
将集合c给当前队列，执行完后是有序的，因为SortedSet 本身就有序，执行完后和 c 有序性一直。
initElementsFromCollection(c);
}
三、方法分析
- 添加元素分析：
//添加元素e
public boolean add(E e) {
//向队列中添加元素
return offer(e);
}
//向队列中添加元素e
public boolean offer(E e) {
//从这里也可看出PriorityQueue不支持 null
if (e == null)
throw new NullPointerException();
//版本+1
modCount++;
//元素将要被添加到的位置索引，即所有元素的末尾位置
int i = size;
//如果将要添加元素的位置 >= 存储元素的数组长度,则需要扩容
if (i >= queue.length)
//扩容
grow(i + 1);
//元素数量 + 1
size = i + 1;
//如果当前元素时第一个被添加到队列中的，则直接赋值给数组第一个位置即可
if (i == 0)
queue[0] = e;
else
//否则对于被添加的新元素进行上滤操作，i：新元素索引位置， e：新元素的值
siftUp(i, e);
//返回添加成功
return true;
}
//扩容，参数为所需要的容量
private void grow(int minCapacity) {
//记录当前队列长度
int oldCapacity = queue.length;
// Double size if small; else grow by 50%
//1.如果当前队列长度小于64，则扩容后的容量为当前容量的两倍 + 2，解 8 -> 8 + 8+2 = 18
//2.如果当前队列长度 大于等于64，则扩容后的容量为当前容量的1.5被，即增加了50%。
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) {
//如果新容量 < 0,则报错
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
//如果新的容量 > Integer.MAX_VALUE - 8，则直接复制Integer.MAX_VALUE,即所能给的最大容量了
//否则复制 MAX_ARRAY_SIZE，注：MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
//堆的上浮/上滤操作
private void siftUp(int k, E x) {
//如果初始化时传入了比较器，则使用传入的比较器来进行上浮操作
if (comparator != null)
siftUpUsingComparator(k, x);
else
//没传入，则使用 E 自己的比较方法比较
siftUpComparable(k, x);
}
//用户传入了比较器的上浮操作
private void siftUpUsingComparator(int k, E x) {
while (k > 0) {
//获取父类节点所在位置的索引
int parent = (k - 1) >>> 1;
//父节点的值
Object e = queue[parent];
//使用传入的比较器进行比较，如果 x >= e,则 当前k位置就是元素 x 的正确位置。
//则可看出，PriorityQueue默认是小顶堆
if (comparator.compare(x, (E) e) >= 0)
break;
//如果 x < e,则将父节点和当前节点值进行交换，达到上浮的操作。这里做了优化，没有立即将x值进行赋值，他是等找到
//x的最终位置，即跳出循环后在将x赋值到正确的位置。
queue[k] = e;
//表示x 的位置替换到了parent了，就是 k 与 父节点交换了位置，达到上浮的效果
k = parent;
}
//将x值复制到正确的位置k上。
queue[k] = x;
}
//用户有传入比较器的上浮操作
private void siftUpComparable(int k, E x) {
//用户没有传入比较器，则使用 E 的比较方法，也可看处 E 如果没有传入比较器，那么必须实现了 Comparable 接口
Comparable<? super E> key = (Comparable<? super E>) x;
//和上面一样的操作，只是一个用传入的比较器比较，一个用 类型E 的比较方法比较
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")
public E peek() {
//堆顶元素即存储在数组索引0位置处，没有元素则返回null
return (size == 0) ? null : (E) queue[0];
}
//获取堆顶元素，即最值. 注意：获取并且移除
public E poll() {
//如果队列为空，返回null
if (size == 0)
return null;
//最末尾元素的位置索引，并且元素个数 - 1，该位置元素用来和堆顶元素进行交换，并且进行下虑操作。
int s = --size;
//版本号 + 1
modCount++;
//获取堆顶元素
E result = (E) queue[0];
//获取最末尾元素
E x = (E) queue[s];
//将最末尾位置置空
queue[s] = null;
//如果整个队列只有一个元素，则无需做下滤操作，否则进行下滤
if (s != 0)
siftDown(0, x);
//返回记录的堆顶元素，即最值
return result;
}
//下滤操作，元素索引位置k，值x
private void siftDown(int k, E x) {
//判断是否传入了比较器，传入了则使用传入的比较器进行下滤
if (comparator != null)
siftDownUsingComparator(k, x);
else
//没有传入比较器，则使用 E 的比较方法进行下滤操作
siftDownComparable(k, x);
}
//使用传入的比较器进行下滤操作，下滤元素索引k，和值x
private void siftDownUsingComparator(int k, E x) {
//下滤就是将元素移动到适合的位置，最多到达非叶子结点，而堆的数据结构是完全二叉树，所以非叶子节点的数量为 size / 2，所以这里使用half
//进行循环判断是否到达最后的非叶子节点，因为一旦到达叶子结点，没有下层可移了，即结束循环。
int half = size >>> 1;
while (k < half) {
//获取当前元素的左子节点
int child = (k << 1) + 1;
//做左子节点的值
Object c = queue[child];
//右子节点的值
int right = child + 1;
//判断左子节点和右子节点谁更大，更小的赋值给child，最后得到的child就是child和right中最小的，只是变量赋值，堆中并不交换位置
if (right < size &&
comparator.compare((E) c, (E) queue[right]) > 0)
c = queue[child = right];
//child 和 当前值x 进行比较，x更大则进行下滤操作，否则结束循环
if (comparator.compare(x, (E) c) <= 0)
break;
//其实就是将x进行下滤操作，循环循环遍历
queue[k] = c;
k = child;
}
//将x值复制到最终确定的位置k出
queue[k] = x;
}
//使用E类的比较方法进行下滤操作，和上面一样，就是判断元素大小一个使用比较器，一个使用E类的比较方法比较，其他没有区别。
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;
}
- 移除元素方法：
//更具元素进行删除，一般PriorityQueue也不用该方法，而是使用 poll（）获取堆顶元素并移除。
public boolean remove(Object o) {
//获取o所在堆中的位置
int i = indexOf(o);
//未发现要删除的o元素，返回删除失败
if (i == -1)
return false;
else {
//否则根据找到的元素下标进行删除
removeAt(i);
//返回删除成功
return true;
}
}
//获取元素o的下标位置
private int indexOf(Object o) {
//元素o为null直接返回-1，表示未找到
if (o != null) {
//没啥好说的，就是数组循环遍历查找
for (int i = 0; i < size; i++)
if (o.equals(queue[i]))
return i;
}
return -1;
}
//删除i位置处的元素
private E removeAt(int i) {
// assert i >= 0 && i < size;
//版本号+1
modCount++;
//获取末尾元素位置，并且元素数量-1，是用来和i位置元素交换，交换后，变成删除最末尾元素，以及i位置元素进行下滤或上滤操作。
int s = --size;
//队列中只有一个元素的情况
if (s == i) // removed last element
queue[i] = null;
else {
//最末尾元素值
E moved = (E) queue[s];
//末尾位置置空
queue[s] = null;
//相当于i位置元素值被最末尾元素给覆盖了，然后现在进行下滤操作
siftDown(i, moved);
//如果moved没有发生下移，则说明moved在i处，后面的元素确实比moved大（moved的合适位置不在后面而是在前面），
//但还不能保证前面的元素比moved小（小顶堆）.
//所以在进行上滤操作
if (queue[i] == moved) {
siftUp(i, moved);
//如果位置发生变化，则表示上滤成功，找到了合适位置，返回末尾元素，该元素返回被用于迭代器中记录于forgetMeNot中，
//作用是如果迭代过程中发生了修改，原先元素位置发生了变化，防止变化位置的元素没有被遍历到，需要记录变化位置的元素，
//并且迭代过程中 从记录这些变换位置的元素集合中 取出需要被遍历的元素。
if (queue[i] != moved)
return moved;
}
}
return null;
}
-
扩容方法：在分析添加元素方法时分析过了。
-
迭代器分析：PriorityQueue只有 Itr 迭代器，不支持迭代过程中队列被修改。
private final class Itr implements Iterator<E> {
/**
* Index (into queue array) of element to be returned by
* subsequent call to next.
*/
//游标，下一个要访问的元素下标位置
private int cursor = 0;
/**
* Index of element returned by most recent call to next,
* unless that element came from the forgetMeNot list.
* Set to -1 if element is deleted by a call to remove.
*/
//上一个被访问元素的下标位置，如果上次没有访问，比如删除操作，则置为-1；
private int lastRet = -1;
/**
* A queue of elements that were moved from the unvisited portion of
* the heap into the visited portion as a result of "unlucky" element
* removals during the iteration. (Unlucky element removals are those
* that require a siftup instead of a siftdown.) We must visit all of
* the elements in this list to complete the iteration. We do this
* after we've completed the "normal" iteration.
*
* We expect that most iterations, even those involving removals,
* will not need to store elements in this field.
*/
//用于记录上滤或者下滤过程中，未被删除且位置发生变化的元素。
private ArrayDeque<E> forgetMeNot = null;
/**
* Element returned by the most recent call to next iff that
* element was drawn from the forgetMeNot list.
*/
//上一个被访问元素的值，记录迭代过程中的上次访问值，如果null则不能进行remove删除，表示上一次没有进行next访问元素，不可remove。
private E lastRetElt = null;
/**
* The modCount value that the iterator believes that the backing
* Queue should have. If this expectation is violated, the iterator
* has detected concurrent modification.
*/
//记录迭代器初始化时队列的版本号（修改计数器，各种叫法吧），判断被修改了则抛出异常
private int expectedModCount = modCount;
//判断是否还有元素可以被遍历
public boolean hasNext() {
return cursor < size ||
(forgetMeNot != null && !forgetMeNot.isEmpty());
}
//迭代获取下一个元素
@SuppressWarnings("unchecked")
public E next() {
//判断队列是否被修改，修改则抛出异常，说明PriorityQueue的迭代器不支持迭代过程中队列被修改。
if (expectedModCount != modCount)
throw new ConcurrentModificationException();
//如果游标还未到末尾元素，则继续迭代获取元素，并更新游标
if (cursor < size)
return (E) queue[lastRet = cursor++];
//游标满了，但是可能有发生位置变化的元素，检查下是否有该类记录,你可能会疑问，上线不是检查了吗，不允许修改，但是并发情况下可能
//在检查后再发生修改。
if (forgetMeNot != null) {
//因为位置发生变化了，所以无法得知记录在这里的元素在堆中的位置，所以设为-1；当然你可遍历获取，但是得不偿失。
lastRet = -1;
//记录这次访问的值，表示这次访问到值了，那么下次remove时则被允许了。
lastRetElt = forgetMeNot.poll();
if (lastRetElt != null)
return lastRetElt;
}
throw new NoSuchElementException();
}
//移除上次被迭代访问的元素
public void remove() {
//判断队列是否被修改，修改则抛出异常，
if (expectedModCount != modCount)
throw new ConcurrentModificationException();
//说明上次迭代得到的元素位置没有发生修改，则更具元素位置删除元素
if (lastRet != -1) {
//删除lastRet位置的元素。
E moved = PriorityQueue.this.removeAt(lastRet);
//表示上次没有元素访问，不允许下次删除了
lastRet = -1;
//成功删除了元素，游标-1
if (moved == null)
cursor--;
else {
//删除失败了，说明元素位置又发生变化了，记录到forgetMenot中。。
if (forgetMeNot == null)
forgetMeNot = new ArrayDeque<>();
forgetMeNot.add(moved);
}
} else if (lastRetElt != null) {
//迭代的过程中元素位置发生变化了，直接更具元素值删除元素
PriorityQueue.this.removeEq(lastRetElt);
lastRetElt = null;
} else {
throw new IllegalStateException();
}
//更新迭代器版本
expectedModCount = modCount;
}
}
四、总结
- 常用于优先级队列，即堆顶元素时优先级最高的/或最低的（看传入的比较器）。不是线程安全的。
- PriorityQueue 默认是小顶堆，是基于数组实现的完全二叉树来构建的堆。拥有完全二叉树的性质。
- 在初始化时，如果基于其他集合构建的 PriorityQueue，则通过自下而上的下滤操作来进行堆化操作，从而调整成为小顶堆。添加元素时，添加至元素尾部，然后通过上滤进行调整，获取堆顶元素时，通过交换尾元素至堆顶，然后经过下滤操作调成成小顶堆。
- 扩容时，如果当前容量 < 64，则扩容为当前容量的两倍 + 2，否则为当前容量的1.5倍。当前也会检查扩容后溢出的情况，最大扩容容量不会超过Integer.MAX_VALUE。
- 迭代过程中不支持队列被修改，有版本号检查机制，但由于 PriorityQueue 不是线程安全的，还是可能导致迭代过程中元素位置被修改，使用了一个集合专门记录修改位置的元素，该集合也会进行迭代获取其中元素。
