PriorityQuene 源码分析
2021-09-24 本文已影响0人
gcno93
PriorityQuene 是最小堆（任意一个非叶子节点的权值，都不大于其左右子节点的权值）实现的，第一个元素就是最小值，想了解最小堆，必须先要了解一下完全二叉树，具体长什么样子，看下图
image.png
这个二叉树有以下特点（重点记住）
假设完全二叉树有一个父节点i,那么他的左子节点就是leftNode = （i*2）+ 1
右子节点 rightNode = （i*2）+ 2
假设有一个节点n ,那它的父节点是 (n-1)/2
size/2-1 的节点都是父节点
成员属性
transient Object[] queue; //可见是数组保存的，但是使用了完全二叉数
private static final int DEFAULT_INITIAL_CAPACITY = 11; //默认11个
/**
* The number of elements in the priority queue.
*/
private int size = 0; //元素个数
/**
* The comparator, or null if priority queue uses elements'
* natural ordering.
*/
private final Comparator<? super E> comparator; //可以传进去一个比较器
/**
* The number of times this priority queue has been
* <i>structurally modified</i>. See AbstractList for gory details.
*/
transient int modCount = 0; // 修改记录数，用于 fail-fast机制，在并发的时候，迭代器会很快的失败
add(E e)
public boolean add(E e) {
return offer(e);
}
public boolean offer(E e) {
if (e == null) //可见不能add null 值
throw new NullPointerException();
modCount++;
int i = size;
if (i >= queue.length) //元素个数大于等于数组的长度
grow(i + 1);
size = i + 1; //元素个数加1
if (i == 0) //若果i = 0 说明是第一个元素
queue[0] = e; //直接插入
else
siftUp(i, e); //不是第一个元素 ，请看下面siftUp函数分析，记住i是元素个数，e是插的值
return true;
}
//---------------------------------------------------扩容-----------------------------------------------------------------------
// 记住：当数组小于64 则是原长度+2 否则 原长度+原长度的一半
private void grow(int minCapacity) { // minCapacity = i + 1 元素个数+1
int oldCapacity = queue.length;
//oldCapacity < 64 如果旧数组长度小于64，则调整长度位 oldCapacity = oldCapacity + 2
//否则是oldCapacity = oldCapacity + oldCapacity >> 1（可理解为oldCapacity / 2） 也就是增长为原来的一半
int newCapacity = oldCapacity + ((oldCapacity < 64) ?
(oldCapacity + 2) :
(oldCapacity >> 1));
//如果大于MAX_ARRAY_SIZE 则hugeCapacity（minCapacity） 看下面的函数分析
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// Arrays.copyOf根据新的数组长度拷贝原数组到新的数组，看下面copyOf()分析
queue = Arrays.copyOf(queue, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
//MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8 = 2147483647 - 8 = 2147483639
//MAX_VALUE = 0x7fffffff; 最大int值 = 2147483647
//大于MAX_ARRAY_SIZE 则等于 MAX_VALUE
//否则等于 MAX_ARRAY_SIZE
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
public static <T> T[] copyOf(T[] original, int newLength) {
//第三个参数 original的class对象
return (T[]) copyOf(original, newLength, original.getClass());
}
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
@SuppressWarnings("unchecked")
T[] copy = ((Object)newType == (Object)Object[].class) //判断是否是Object类型
? (T[]) new Object[newLength] //Object类型
//Array.newInstance方法创建一个具有指定组件类型和长度的新数组。
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
//这里就是拷贝数组了，可以看我的另外一个博文，这里就不说了
//original 原数组
//0 拷贝原数组开始位置
//copy 目标数组
// Math.min(original.length, newLength) 取最小值，这里肯定是original.length
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
//返回
return copy;
}
//---------------------------------------------------扩容-----------------------------------------------------------------------
//---------------------------------------------------siftUp-----------------------------------------------------------------------
private void siftUp(int k, E x) { //记住k是元素个数，e是插的值
if (comparator != null) //看你定没定义comparator ，可以在new PriorityQuene(）中传一个比较器
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x); //使用默认的比较器
}
private void siftUpComparable(int k, E x) {
//如果是String ,String 类型实现了 Comparable可以强转，如果是自定义的，需要实现Comparable，或者你自己在 new PriorityQuene(）中传一个比较器
Comparable<? super E> key = (Comparable<? super E>) x;
//记住k是元素个数，e是插的值
//第一次必须大于0啊，是0不就是上面处理了吗 第一个元素直接 queue[0] = e
//至于其他次，看下面
while (k > 0) {
//记得上面需要记得的完全二叉树的公式吗？
//第一次进来的时候，k等于元素个数，不就是最后一个元素 他的下标=(k-1)/2，就是最后一个元素的父节点吗？
//当然这是循环，可能执行多次，但是，这里的意思，不就是找某个节点的父节点下标吗？
int parent = (k - 1) >>> 1;
//取出父节点的值·
Object e = queue[parent];
//记住小堆顶的定义-任意一个非叶子节点的值，都不大于其左右子节点的值
//如果这个插入值比父元素要大或者等于，不就说明了，他可以插入k这个位置吗
//否则 说明比父节点要小，那他就要把父节点放到k，自己准备上位到父节点的位置上，
//记得我只是说准备，不一定能，要一直循环直到找到能放自己的地方
if (key.compareTo((E) e) >= 0)
break;
//如果是可以插入k，这个不会执行
//如果执行，就是比父节点还要小，则把父节点放到k节点上，自己准备上位到父节点的位置上
queue[k] = e;
//k的位置就是父节点的下标了，继续判断父节点的父节点是否小于自己
k = parent;
}
queue[k] = key; // k就是key能放的位置，yes,yes
}
//---------------------------------------------------siftUp-----------------------------------------------------------------------
peek() 获取但不删除队首元素，也就是队列中权值最小的那个元素
public E peek() {
return (size == 0) ? null : (E) queue[0]; //空返回null 否则，取数组第一个元素
}
element() 获取但不删除队首元素，也就是队列中权值最小的那个元素，跟peek()比较只是null 会抛异常
public E element() {
E x = peek(); //直接调peek（）
if (x != null) //不是null 返回
return x;
else //null 抛异常
throw new NoSuchElementException();
}
remove() and poll()获取并删除队首元素,区别是当方法失败时前者抛出异常，后者返回null
public E remove() {
E x = poll(); //主要看这个
if (x != null) //不是null 返回
return x;
else //null 抛异常
throw new NoSuchElementException();
}
public E poll() {
if (size == 0) //没有元素
return null; //返回null
int s = --size; //--size，元素个数先自减1，s = size-1
modCount++; //修改次数+1
E result = (E) queue[0]; // 记录第一个元素
E x = (E) queue[s]; //记录最后一个元素
queue[s] = null; // 最后一个元素变成空的
if (s != 0) //不是只有一个元素的
siftDown(0, x); //进去调整数
return result;
}
private void siftDown(int k, E x) {
//记得第一次 k =0 x=最后一个元素的值
if (comparator != null)
siftDownUsingComparator(k, x); //看你定没定义comparator ，可以在new PriorityQuene(）中传一个比较器
else
siftDownComparable(k, x); //使用默认的比较器
}
private void siftDownComparable(int k, E x) {
//记得第一次 k =0 x=最后一个元素的值
//如果是String ,String 类型实现了 Comparable可以强转，如果是自定义的，需要实现Comparable，
//或者你自己在 new PriorityQuene(）中传一个比较器
Comparable<? super E> key = (Comparable<? super E>)x;
//记得上面需要记得的完全二叉树的公式吗？
// size/2-1 就是所有的父节点下标
//举个例子 size = 12 则 所有的父节点 = 12/2 -1 =5 也就是 0,1,2,3,4,5是父节点
int half = size >>> 1;
//k的下标 不可能不是父节点，否则结束循坏
//上面的例子举例，size >>> 1 可以等于 12/2 = 6 ,所以 k = 0,1,2,3,4,5才能进这个循环
//第一次进来循坏，k==0
while (k < half) {
int child = (k << 1) + 1; // k的左子节点 左节点公式 =（父节点*2）+ 1
Object c = queue[child];//取出k的左子节点
int right = child + 1;// k的右子节点 child =（父节点*2）+ 1 所以 right = （父节点*2）+ 1 +1
//如果没有右节点就不比较了，这里只是想把k的两个子节点的最小值节点赋给c
//child =最小值节点的的下标
if (right < size &&
((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
c = queue[child = right];
//如果key比k的最小值的子节点的值小，则说明k就是key需要插入的地方
//否则，说明key的值大，就把小的节点飘上去
//还记得我们是remove()删除第一个元素，第一次循环k==0
//如果key 比第一个元素的左右节点都小，那么k=0 不就是=key 了吗？
if (key.compareTo((E) c) <= 0)
break;
queue[k] = c; //那么k的位置就给最小值，让最小值的节点飘上去，
//k =最小值的下标，如果k 还是父节点继续循环比较k的左右节点的最小值节点是否比key的大，大的话k就是放key的地方，否则继续循坏
//不明白的看一下，下面的图
k = child;
}
queue[k] = key;
}
image.png
image.png
image.png
image.png
image.png
image.png
image.png
不知明白了不
remove(Object o) 删除队列中跟o相等的某一个元素(如果有多个相等，只删除一个)
public boolean remove(Object o) {
int i = indexOf(o); //找出下标，可以看下面的函数
if (i == -1)
return false; //找不到 -1
else {
removeAt(i); //这个才是关键，看下面的分析
return true;
}
}
private int indexOf(Object o) {
if (o != null) { //不是null
for (int i = 0; i < size; i++) //循环找啊找！！！！
if (o.equals(queue[i]))
return i;
}
return -1; //null 找不到 返回-1
}
private E removeAt(int i) {
// assert i >= 0 && i < size;
modCount++; //修改的次数+1
int s = --size; //元素个数给减一
if (s == i) // 删除最后一个元素
queue[i] = null;
else { //不是最后一个元素
E moved = (E) queue[s]; //取出最后的元素
queue[s] = null;//最后的元素被删了
siftDown(i, moved);//上面的remove()已经讲过了，这里不重复了
if (queue[i] == moved) { //删的地方就是可以放最后一个元素的地方，那就再确定一下i的父类是否正确
siftUp(i, moved);//add的时候已经解析
//不是一样，返回moved，
if (queue[i] != moved)
return moved;
}
}
return null;
}
