- 新年第一篇, 如果有错误请及时指正哈!! 祝大家新年快乐 嘻嘻
- 今天说一下
PriorityQueue,这是一个有顺序的队列,此顺序并不是加入顺序,而是元素的按一定规则排列的顺序,我们看一下他的类图关系
-
相对于
Deque,此实现就只是实现了关于Queue的相关接口,所以它就只能作为队列使用了.我们来稍微看一下用法Comparator<Integer> comparator = Comparator.comparingInt(x -> x); PriorityQueue<Integer> queue = new PriorityQueue<>(comparator); queue.add(7); queue.add(1); queue.add(10); queue.add(6); System.out.println(queue); System.out.println(queue.poll()); System.out.println(queue.poll()); System.out.println(queue.poll()); System.out.println(queue.poll()); -
结果
[1, 6, 10, 7] 1 6 7 10 - 我们可以看到,在添加后,队列中的元素并没有马上进行顺序排列,但也不同于加入顺序(之后会提到为啥会是这么个输出顺序,其实这是已经排序好了),然后在我们取值的时候才会按照顺序取出元素,并且他的构造可以自定义比较规则
- 我们依旧从他的属性开始
属性
//默认初始容量
private static final int DEFAULT_INITIAL_CAPACITY = 11;
//用数组保存元素
transient Object[] queue;
int size;
//用于队列元素比较
private final Comparator<? super E> comparator;
//关于fast-fail机制
transient int modCount; - 并没有出现什么特别的属性,我们接着看他的构造
构造
-
此类的构造方法比较多,有如下几个
PriorityQueue() //默认大小初始化 PriorityQueue(int) //指定大小初始化 PriorityQueue(Comparator) //指定比较器初始化 PriorityQueue(int,Comparator) //指定比较器和初始化容量 PriorityQueue(Collection) //将collection内元素作为参数初始化 PriorityQueue(StoredSet) //将排列好的set作为初始化 -
我们依次来看他的构造方法的源码
public PriorityQueue() { this(DEFAULT_INITIAL_CAPACITY, null); } public PriorityQueue(int initialCapacity,Comparator<? super E> comparator) { if (initialCapacity < 1) throw new IllegalArgumentException(); //很简单了,就是进行new和赋值动作 this.queue = new Object[initialCapacity]; this.comparator = comparator; } - 对于上面的构造很简单,所以不需要太多解释,那么这是无参的构造过程,从这我们也就可以推断出,当构造是
int,是Comparator的时候,无非就是将int参数为初始容量,然后默认比较器,或者以Comparator为参的时候,是以默认的构造容量来初始化数组的 -
所以我们就直接看以
Collection和StoredSet为参的构造方法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 { //既不是排序的SortedSet,也不是PriorityQueue //那么就按照普通的Collection初始化 this.comparator = null; initFromCollection(c); } } -
上面逻辑很简单,目的只是区分
Collection的实现,来进行分类的初始化,当是SortedSet实现类的时候的初始化逻辑如下private void initElementsFromCollection(Collection<? extends E> c) { Object[] es = c.toArray(); int len = es.length; // 如果c.toArray错误地没有返回Object[],就复制它 if (es.getClass() != Object[].class) es = Arrays.copyOf(es, len, Object[].class); //如果集合只有一个元素,或者comparator不等于null if (len == 1 || this.comparator != null) //目的是寻找是否有null //所以从这也可以看出来,此队列的实现是不允许插入null的 for (Object e : es) if (e == null) throw new NullPointerException(); //确保下标0元素存在 this.queue = ensureNonEmpty(es); this.size = len; } private static Object[] ensureNonEmpty(Object[] es) { //如果集合元素大于0,那么就返回集合就好,否则就是空的,那么就返回一个空数组,容量为1 return (es.length > 0) ? es : new Object[1]; } -
如果判断了
Collection的实现是PriorityQueue,那么初始化过程就变成了这样private void initFromPriorityQueue(PriorityQueue<? extends E> c) { //确保类型 if (c.getClass() == PriorityQueue.class) { //如果下标为0的元素存在 this.queue = ensureNonEmpty(c.toArray()); this.size = c.size(); } else { initFromCollection(c); } } //使用给定集合中的元素初始化队列数组 private void initFromCollection(Collection<? extends E> c) { //这的实现已经在上面说明了 initElementsFromCollection(c); //算法的具体实现 //实现了在调用前不考虑元素顺序 //在整个树中建立堆不变量(这的解释来自翻译源注释) heapify(); } - 当
instanceof判断为PriorityQueue时,进入初始化PriorityQueue的逻辑,首先确保头元素存在,这是为了保证peek()和poll()方法的正常使用,如果不是PriorityQueue.class,那么就按照普通的Collection初始化,只不过普通的Collection不具备PriorityQueue的特性,所以使用heapify方法加以辅助 - 在这总结一下参数为
Collection的构造方法,其先去判断类型之间是否存在联系,然后按照不同类型去区别对待,由于SortedSet已经具备了有序的元素,所以只需要简单的确认即可初始化为PriorityQueue,当遇到PriorityQueue的实现的时候,那么如果具体实现类是PriorityQueue.class,那么就直接确认元素直接赋值即可,否则就按照普通Collection初始化,由于普通的Collection不具备PriorityQueue排序的特性,所以使用heapify方法加以辅助,然后完成参数为Collection的初始化逻辑 - 上面的
heapify方法,提到了整个树中的堆这么几个字眼,所以PriorityQueue也是使用树来做存储结构的,这也就解释了为什么可以做到不排序(只是输出结果中好像是不排序的),而在取出的时候依旧可以按照顺序取出,这里所说的不排序是指直接输出对象后的String字符串里的元素看似是不排序的,但其实这个字符串也是已经排序好的(按照树节点的顺序存储,也就是文章开始提到的不是add顺序保存的),可以参考我的 二叉树,既然PriorityQueue使用数组存储树结构,那么这个树肯定就是一个完全二叉树,因为这样的树结构可以保证使用数组存储的效率是最高的,不存在浪费的 - 完全二叉树在数组中保存, 图取自 CSDN
-
下面是参数为
SortedSet的初始化构造逻辑public PriorityQueue(SortedSet<? extends E> c) { this.comparator = (Comparator<? super E>) c.comparator(); //已经说过其实现过程了在上面 initElementsFromCollection(c); } - 至此构造器部分就结束了
- 对于队列操作,那么最核心的就是
remove和add方法,当然还有offer和poll,鉴于他们的细微差别,那么我们就拿remove和add方法来说好了
add
public boolean add(E e) {
//.....还是调offer
return offer(e);
}
public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
modCount++;
//queue中的元素个数
int i = size;
//queue满了
if (i >= queue.length)
//增长,里面去详细计算了增长个数和怎么去增长的
grow(i + 1);
//核心方法,从下往上调整堆
siftUp(i, e);
size = i + 1;
return true;
}
//跟ArrayDeque差不多
private void grow(int minCapacity) {
int oldCapacity = queue.length;
// 跟ArrayDeque中实现一样
//如果queue小的话要加倍.否则增长50%
//10 >> 1 = 5
int newCapacity = oldCapacity + ((oldCapacity < 64) ?
(oldCapacity + 2) :
(oldCapacity >> 1));
//如果计算后预计的容量 大于 数组最大值
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
queue = Arrays.copyOf(queue, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
//因为如果数组达到最大值,当上面offer方法传入grow(i+1)时
//i就已经等于Integer.MAX_VALUE
//当int i = Integer.MAX_VALUE + 1计算后结果就是一个负数,说明超过int值的范围了
if (minCapacity < 0)
//内存溢出
throw new OutOfMemoryError();
//判断计划初始化后的容量是否大于最大值,是的话将数组扩展到Integer.MAX_VALUE个容量
//否则就返回MAX_ARRAY_SIZE个容量
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}-
核心方法
/* Inserts item x at position k, maintaining heap invariant by * promoting x up the tree until it is greater than or equal to * its parent, or is the root. */ //在位置k处插入x,保持堆不变,向上提升x,直到其大于或等于它的父级或者是根 private void siftUp(int k, E x) { //使用到的这两个方法区别在于一个指定了比较器一个没有 //如果指定了可能就会影响树的排序 //默认都是小顶堆 //都是去调整树 if (comparator != null) siftUpUsingComparator(k, x, queue, comparator); else siftUpComparable(k, x, queue); } //就是当前元素与父节点不断比较如果比父节点小就交换然后继续向上比较,否则停止比较的过程 private static <T> void siftUpUsingComparator( int k, T x, Object[] es, Comparator<? super T> cmp) { while (k > 0) { int parent = (k - 1) >>> 1; Object e = es[parent]; if (cmp.compare(x, (T) e) >= 0) break; es[k] = e; k = parent; } es[k] = x; } //跟上面实现的作用是一样的 private static <T> void siftUpComparable(int k, T x, Object[] es) { Comparable<? super T> key = (Comparable<? super T>) x; while (k > 0) { int parent = (k - 1) >>> 1; Object e = es[parent]; if (key.compareTo((T) e) >= 0) break; es[k] = e; k = parent; } es[k] = key; } - 到这add方法大概的流程就说完了,来看remove
remove
public boolean remove(Object o) {
//indexOf传入对象,返回对象在数组中的位置
int i = indexOf(o);
//表示不存在该元素
if (i == -1)
return false;
else {
removeAt(i);
return true;
}
}
E removeAt(int i) {
// assert i >= 0 && i < size;
final Object[] es = queue;
modCount++;
//更改元素属性并保存位置
int s = --size;
if (s == i) // removed last element
es[i] = null;
else {
//就不是删除最后一元素
//暂时保存要删除元素
E moved = (E) es[s];
es[s] = null;
//开始调整整个树结构
siftDown(i, moved);
if (es[i] == moved) {
siftUp(i, moved);
if (es[i] != moved)
return moved;
}
}
return null;
}- 其实这也是比较简单的,前提是我们大致了解了二叉树的知识,以及了解为什么可以使用数组来保存二叉树的数据,那么知道了这些后,删除操作也就是取得节点在数组中位置然后赋值为null.然后在调整树,如果元素是最后的位置,那么就不需要调整树了,因为他是叶结点
- 这个类最主要的就是其存储结构了,我们需要重点掌握其思想.可以参考我的二叉树的介绍或者这篇 内容去了解一下怎么去调整树的,这样我们就能基本了解了这个有序队列的核心内容了
