平面设计的网站有哪些网站,廊坊建设局网站6,广州seo网站推广顾问,贸易网站建设公司PriorityQueue集合源码分析 文章目录 PriorityQueue集合源码分析前置知识一、字段分析二、构造函数分析三、方法分析四、总结 PriorityQueue 优先级队列#xff0c;是基于堆的结构来构建的。而堆是基于完全二叉树来实现的#xff0c;而二叉树除了可以用节点来实现也可以用数组…PriorityQueue集合源码分析 文章目录 PriorityQueue集合源码分析前置知识一、字段分析二、构造函数分析三、方法分析四、总结 PriorityQueue 优先级队列是基于堆的结构来构建的。而堆是基于完全二叉树来实现的而二叉树除了可以用节点来实现也可以用数组实现就是将二叉树按照层序便利填充到数组中父节点i那么左子节点为2*i 1, 右子节点为 2 * i 2i 指数组索引而PriorityQueue就是基于用数组实现的完全二叉树来实现的堆。PriorityQueue 默认是小顶堆。
前置知识
堆是一棵完全二叉树。节点总数为n那么非叶子节点数为 n/2叶子节点数为 n 1/ 2。堆中的任意一个非叶子节点的值总是不大于小顶堆或不小于大顶堆任意儿子节点的值。堆中每个子树也可看做成一个堆。更多堆的基础知识可查看这篇介绍堆介绍熟悉堆的性质与操作后学习 PriorityQueue就很简单了。这里简单实现下大顶堆
package com.example.demo.heap;import java.util.Comparator;/*** 大顶堆的简单实现** param E*/
public class BinaryHeapE implements HeapE {private E[] elements;private int size;private ComparatorE comparator;private static final int DEFAULT_CAPACITY 10;public BinaryHeap(ComparatorE 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): ((ComparableE )e1).compareTo(e2);}Overridepublic int size() {return size;}Overridepublic boolean isEmpty() {return size 0;}Overridepublic void clear() {for (int i 0; i size; i) {elements[i] null;}size 0;}Overridepublic 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];}//获取堆顶元素Overridepublic E get() {emptyCheck();return elements[0];}//删除堆顶元素。 交换删除 下浮Overridepublic 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 / 2int 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;}Overridepublic 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;//获取该集合的比较器并赋给PriorityQueuethis.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 doesnt return Object[], copy it.//比如ListString 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子类那可能存在问题了要进行堆化操作并检查元素中是否有nullinitFromCollection(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不支持 nullif (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 82 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) // overflowthrow new OutOfMemoryError();//如果新的容量 Integer.MAX_VALUE - 8则直接复制Integer.MAX_VALUE,即所能给的最大容量了//否则复制 MAX_ARRAY_SIZE注MAX_ARRAY_SIZE Integer.MAX_VALUE - 8return (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位置处没有元素则返回nullreturn (size 0) ? null : (E) queue[0];}//获取堆顶元素即最值. 注意获取并且移除
public E poll() {//如果队列为空返回nullif (size 0)return null;//最末尾元素的位置索引并且元素个数 - 1该位置元素用来和堆顶元素进行交换并且进行下虑操作。 int s --size;//版本号 1modCount;//获取堆顶元素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-leafwhile (k half) {int child (k 1) 1; // assume left child is leastObject 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;//版本号1modCount;//获取末尾元素位置并且元素数量-1是用来和i位置元素交换交换后变成删除最末尾元素以及i位置元素进行下滤或上滤操作。int s --size;//队列中只有一个元素的情况if (s i) // removed last elementqueue[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 IteratorE {/*** 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 weve completed the normal iteration.** We expect that most iterations, even those involving removals,* will not need to store elements in this field.*///用于记录上滤或者下滤过程中未被删除且位置发生变化的元素。private ArrayDequeE 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;//成功删除了元素游标-1if (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 不是线程安全的还是可能导致迭代过程中元素位置被修改使用了一个集合专门记录修改位置的元素该集合也会进行迭代获取其中元素。
