欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

java集合 PriorityQueue原理, 通过源码学习进行深入了解

程序员文章站 2022-06-30 19:40:23
PriorityQueue基于jdk8源码学习概述原理继承关系成员变量构造函数扩容关键方法siftDown 和 siftUpheapify 和 removeAtadd 和 offerelement 和 peekremove 和 pollPriorityQueue 小结参考:概述一个基于优先级堆的*优先级队列。根据 Comparable 比较器的自然顺序确定优先级元素的排列顺序,或者根据构造队列时创建的 Comparator 比较器排列队列元素。优先级队列不允许 null 元素。依赖于自然顺序的优先级队...

概述

一个基于优先级堆的*优先级队列。根据 Comparable 比较器的自然顺序确定优先级元素的排列顺序,或者根据构造队列时创建的 Comparator 比较器排列队列元素。优先级队列不允许 null 元素。依赖于自然顺序的优先级队列 也不允许插入不可比较的对象(这样做可能抛出 ClassCastException 异常)。
队列的头部元素是于指定顺序相关的最小的元素。如果多个元素满足该条件,那么头部元素是其中任意一个。队列的检索操作 poll, remove, peek, element 等会访问队列的头部元素。
注意该实现不是同步的。多线程不应该同时修改优先级队列,而应该使用线程安全的 PriorityBlockingQueue 类。
此实现提供了时间代价为 O(log(n)) 的入队和出队方法:offer, poll, remove, add;提供了线性时间代价的 remove 和 contains 方法;除此之外,还有常数时间代价的 peek, element, size 方法。

原理

Java中PriorityQueue实现了Queue接口,不允许放入null元素;其通过堆实现,具体说是通过完全二叉树(complete binary tree)实现的小顶堆(任意一个非叶子节点的权值,都不大于其左右子节点的权值),也就意味着可以通过数组来作为PriorityQueue的底层实现。
实现的原理图如下:
java集合 PriorityQueue原理, 通过源码学习进行深入了解
上图中我们给每个元素按照层序遍历的方式进行了编号,如果你足够细心,会发现父节点和子节点的编号是有联系的,更确切的说父子节点的编号之间有如下关系:

leftNo = parentNo*2+1

rightNo = parentNo*2+2

parentNo = (nodeNo-1)/2

通过上述三个公式,可以轻易计算出某个节点的父节点以及子节点的下标。这也就是为什么可以直接用数组来存储堆的原因。

PriorityQueue的peek()和element操作是常数时间,add(), offer(), 无参数的remove()以及poll()方法的时间复杂度都是log(N)。

继承关系

它是java集合框架中的一员,它的继承关系是:
java集合 PriorityQueue原理, 通过源码学习进行深入了解

继承于抽象队列类,即PriorityQueue实现了基本的队列操作和集合操作。
实现了Serializable接口,说明该类可以序列化。

成员变量

默认初始容量为11,即未指定初始容量的构造函数创建队列时,初始容量为11。
可分配的最大的数组容量为Integer.MAX_VALUE - 8。
queue则是优先队列的底层数组。

 private static final long serialVersionUID = -7720805057305804111L;
   //序列化,比较版本用的,对类功能没有影响
 
 /* The maximum size of array to allocate.
     *  数组最多能容纳的元素个数。
     * Some VMs reserve some header words in an array.
     * Attempts to allocate larger arrays may result in
     * OutOfMemoryError: Requested array size exceeds VM limit
     * 些虚拟机会保留一些头消息,占用部分空间。
     *   尝试分配比这个值更大的空间可能会抛出 OutOfMemoryError 错误:请求的
     *  数组大小超过了虚拟机的限制。
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    private static final int DEFAULT_INITIAL_CAPACITY = 11;
     //默认的初始容量
    /**
     * Priority queue represented as a balanced binary heap: the two
     * children of queue[n] are queue[2*n+1] and queue[2*(n+1)].  The
     * priority queue is ordered by comparator, or by the elements'
     * natural ordering, if comparator is null: For each node n in the
     * heap and each descendant d of n, n <= d.  The element with the
     * lowest value is in queue[0], assuming the queue is nonempty.
     *
     * 优先级队列表现为一个平衡的二进制堆:queue[n] 的两个子队列分别为
     * queue[2*n+1] 和 queue[2*(n+1)]。如果队列的顺序由比较器决定,或者按
     * 元素的自然顺序排序。对于堆中的每个节点 n 和 n 的每个后代 d,有 n <= d。
     * 假定队列非空,堆中最小值的元素为 queue[0]。
     */
    transient Object[] queue; // non-private to simplify nested class access
    //非私有以简化嵌套类访问
    /**
     * The number of elements in the priority queue.
     * 优先级队列中的元素个数。
     */
    private int size = 0;

    /**
     * The comparator, or null if priority queue uses elements'
     * natural ordering.
     * 比较器。如果使用元素的自然顺序排序的话此比较器为 null。
     */
    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; // non-private to simplify nested class access
    

构造函数

有7个构造函数:
提供了可以指定初始容量和比较器的(可以同时指定,也可以都不指定,也可以指定其中一个)4个构造函数。
提供使用优先队列PriorityQueue和SortedSet类集合,或者普通集合 作为初始队列元素的3个构造方法。
未指定初始容量,使用DEFAULT_INITIAL_CAPACITY=11作为初始数组queue的长度。
未指定比较器comparator,则comparator为null。

/**
     * 创建一个容量为默认初始容量的优先级队列。其中元素的顺序为
     * Comparable 自然顺序。
     */
    public PriorityQueue() {
        this(DEFAULT_INITIAL_CAPACITY, null);
    }

    /**
     * 创建一个特定初始容量的优先级队列,其中元素的顺序为 Comparable 的
     * 自然顺序。
     * @param initialCapacity the initial capacity for this priority queue
     * @throws IllegalArgumentException if {@code initialCapacity} is less
     *         than 1
     */
    public PriorityQueue(int initialCapacity) {
        this(initialCapacity, null);
    }

    /**
     *创建一个容量为默认初始容量,元素排列顺序为比较器指定顺序的优先级
     *     队列。
     * @param  comparator the comparator that will be used to order this
     *         priority queue.  If {@code null}, the {@linkplain Comparable
     *         natural ordering} of the elements will be used.
     * @since 1.8
     */
    public PriorityQueue(Comparator<? super E> comparator) {
        this(DEFAULT_INITIAL_CAPACITY, comparator);
    }

    /**
     *创建一个容量为默认初始容量,元素排列顺序为比较器指定顺序的优先级
     * 队列。
     * @param  initialCapacity the initial capacity for this priority queue
     * @param  comparator the comparator that will be used to order this
     *         priority queue.  If {@code null}, the {@linkplain Comparable
     *         natural ordering} of the elements will be used.
     * @throws IllegalArgumentException if {@code initialCapacity} is
     *         less than 1
     */
    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
        if (initialCapacity < 1)     //指定容量小于1,抛出异常,注意不允许指定容量为0
            throw new IllegalArgumentException();
        this.queue = new Object[initialCapacity];       //创建新数组
        this.comparator = comparator;       //比较器赋值
    }

    /**
     *创建一个包含指定集合所有元素的优先级队列。如果指定集合是一个
     *  SortedSet 的实例或者是另一个 PriorityQueue,这个优先级队列中的元素
     *  会以相同的顺序排列。否则,这个优先级队列将根据元素的自然顺序排列。
     * @param  c the collection whose elements are to be placed
     *         into this priority queue
     * @throws ClassCastException if elements of the specified collection
     *         cannot be compared to one another according to the priority
     *         queue's ordering
     * @throws NullPointerException if the specified collection or any
     *         of its elements are null
     */
    @SuppressWarnings("unchecked")
    public PriorityQueue(Collection<? extends E> c) {
        if (c instanceof SortedSet<?>) {      //判断是否是SortedSet
            SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
            this.comparator = (Comparator<? super E>) ss.comparator();   //赋值比较器
            initElementsFromCollection(ss);    //排序set版本的初始化值
        }
        else if (c instanceof PriorityQueue<?>) { //判断是否是PriorityQueue
            PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
            this.comparator = (Comparator<? super E>) pq.comparator();//赋值比较器
            initFromPriorityQueue(pq);    //优先队列的初始化值
        }
        else {      //如果不是可排序的,则使用默认比较器
            this.comparator = null;   //   即比较器赋值为null
            initFromCollection(c);   //普通集合版本的初始化值
        }
    }

    /**
     *创建一个包含指定集合所有元素的优先级队列。这个优先级队列中的元素
     *   会以指定队列相同的顺序排序。
     * @param  c the priority queue whose elements are to be placed
     *         into this priority queue
     * @throws ClassCastException if elements of {@code c} cannot be
     *         compared to one another according to {@code c}'s
     *         ordering
     * @throws NullPointerException if the specified priority queue or any
     *         of its elements are null
     */
    @SuppressWarnings("unchecked")
    public PriorityQueue(PriorityQueue<? extends E> c) {    //和上面传入集合是优先队列时候处理一样
        this.comparator = (Comparator<? super E>) c.comparator();
        initFromPriorityQueue(c);
    }

    /**
     *创建一个包含指定 SortedSet 的所有元素的优先级队列。这个优先级队列
     *  中的元素以给定 SortedSet 的顺序排列。
     * @param  c the sorted set whose elements are to be placed
     *         into this priority queue
     * @throws ClassCastException if elements of the specified sorted
     *         set cannot be compared to one another according to the
     *         sorted set's ordering
     * @throws NullPointerException if the specified sorted set or any
     *         of its elements are null
     */
    @SuppressWarnings("unchecked")
    public PriorityQueue(SortedSet<? extends E> c) {      //和上面传入集合是排序set时处理一样。
        this.comparator = (Comparator<? super E>) c.comparator();
        initElementsFromCollection(c);
    }


使用不同类型集合创建优先队列时,会调用的三个方法:

  // 根据给定的优先级队列初始化此优先级队列,将所有元素复制到此队列中
    // 直接将给定的优先级队列转化为数组,赋值给此队列
    private void initFromPriorityQueue(PriorityQueue<? extends E> c) {  //优先队列版本的初始化值
        if (c.getClass() == PriorityQueue.class) {   //先判断传入的是否是优先队列类
            this.queue = c.toArray();   //是的话,将指定优先队列转化为数组,赋值给当前队列底层数组queue
            this.size = c.size();
        } else {
            initFromCollection(c);      //如果发现不是优先队列,调用普通集合版本的初始化方法
        }
    }
    // 根据给定的 Collection 初始化此优先级队列,将所有元素复制到此队列中
    private void initElementsFromCollection(Collection<? extends E> c) {  //SortedSet版本,普通集合也会调用到
        Object[] a = c.toArray();    //得到集合的数组。
        // If c.toArray incorrectly doesn't return Object[], copy it.
        //如果不是返回Object数组,则使用Array.copyOf进行类型转化。
        if (a.getClass() != Object[].class)
            a = Arrays.copyOf(a, a.length, Object[].class);
        int len = a.length;     //得到元素个数
        if (len == 1 || this.comparator != null)  //有排序功能集合,或者只有一个元素的集合执行检查空值。
            for (int i = 0; i < len; i++)   //判断集合得到的数组是否全不为null,因为优先队列不允许元素为null,
                if (a[i] == null)  //只要有一个为null,就会抛出空指针异常
                    throw new NullPointerException();
        this.queue = a;
        this.size = a.length;     //排完序的集合初始化到这步就完成。
    }

    /**
     * Initializes queue array with elements from the given Collection.
     * 根据给定的集合中的元素初始化此队列。普通集合版本,
     * @param c the collection
     */
    private void initFromCollection(Collection<? extends E> c) {  //普通集合版本
        initElementsFromCollection(c);
        heapify();              //堆处理
    }

扩容

PriorityQueue,底层实现时数组,和集合框架中使用数组作为底层结构的类一样,都需要考虑扩容的问题,即在元素添加到数组之前,需要判断数组容量是否够,以及不够时候,怎么进行扩容。PriorityQueue类中使用了grow方法,该方法主要在add 和 offer添加元素时,如果容量不够就要调用此方法扩容。
扩容结果:
如果就容量小于64,则新容量为老容量*2+2。
如果大于等于64,则扩容为老容量的1.5倍。
如果新容量超出MAX_ARRAY_SIZE ,则判断minCapacity是否超出MAX_ARRAY_SIZE ,
超出则用 Integer.MAX_VALUE,否则用MAX_ARRAY_SIZE。

 /**
     * Increases the capacity of the array.
     *扩大数组的容量
     * @param minCapacity the desired minimum capacity
     */
    private void grow(int minCapacity) {
        int oldCapacity = queue.length;    //记录旧容量
        // Double size if small; else grow by 50%
        //如果容量小于64,则扩容的新容量为2*老容量+2,
        //否则新容量为老容量的1.5倍。
        //因为容量都是+1然后判断,并且最小容量为1,则扩容以后的新容量肯定大于minCapacity
        //这和ArrayList不同,不需要判断扩容以后,新容量是否大于minCapacity
        int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                (oldCapacity + 2) :
                (oldCapacity >> 1));
        // overflow-conscious code
        // 如果新容量比规定的最大容量还要大,那么将新容量设置为整型最大值
        if (newCapacity - MAX_ARRAY_SIZE > 0)     //如果扩容大于最大允许的数组长度
            newCapacity = hugeCapacity(minCapacity); //调用hugeCapacity进行判断。
        queue = Arrays.copyOf(queue, newCapacity);   //同样适用Array.copyOf进行复制。
    }
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // 溢出
            throw new OutOfMemoryError();
        // 指定容量大于规定的最大容量,将新容量设置为整型最大值,否则设置
        // 为规定的最大容量。
        return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
    }

关键方法

主要是队列方法,但是每一步对优先队列的结构修改都要维护最小堆/最大堆的结构。
维护结构的主要方法是siftDown和siftUp。
而如果从一个无序集合创建优先队列,还需要调用heapify,建立整个最小堆/最大堆。

siftDown 和 siftUp

(1)siftUp方法,即插入一个值为x的元素到k位置时,因为优先队列要维护最小堆的结构,所以需要上移和下移元素,而siftUp,则是上移操作,它的原理图是:
java集合 PriorityQueue原理, 通过源码学习进行深入了解
即当元素添加到队列末尾时,需要上调至合适位置以满足整个数组时最小堆的结构。即在最小堆中任意父节点要小于等于其孩子节点的值。
所以siftUp移动的原理是,从插入位置k开始,通过parent=(k-1)>>>1,获得父节点的索引位置。
然后判断插入值是否大于等于父节点值,如果满足,则说明已经是最小堆结构,停止循环。
如果不满足,说明,需要将当前父节点下放到k位置,然后k更新为parent,下次循环将取此次循环的父节点的父节点进行比较,这样就实现了将插入位置层层上移的过程。
知道满足插入值大于等于父节点值,就停下,此时的k就是插入值应该放置在优先队列中的索引。
源码实现如下:
注意:根据是否指定了比较器,分为两个siftUp方法,而这两个方法原理相同,只是比较时代码略有不同

 /**
     * 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(从 k 位置开始调整堆,找到元素 x 的位置,忽略
     * 原先 k 位置的元素),通过向上提升 x 直到它大于等于它的父元素或者
     *   根元素,来保证满足堆成立的条件。
     * To simplify and speed up coercions and comparisons. the
     * Comparable and Comparator versions are separated into different
     * methods that are otherwise identical. (Similarly for siftDown.)
     *为了简化和加速强制转换和比较,Comparable(元素的默认比较器)
     * 和 Comparator(指定的比较器)被分成不同的方法,这两个方法基本
     * 等同。(siftDown 同理)
     * @param k the position to fill
     * @param x the item to insert
     */
    private void siftUp(int k, E x) {
        if (comparator != null)       //有指定的比较器。
            siftUpUsingComparator(k, x);
        else        //如果没有指定,即元素实现了Comparable接口,则使用元素默认比较器。
            siftUpComparable(k, x);
    }

    @SuppressWarnings("unchecked")
    //传入的参数是,出插入的x,和填充到队列中的初始位置k。
    private void siftUpComparable(int k, E x) {   //元素默认比较器的向上移动插入元素的版本。
        // <? extends E>,集合中元素类型上限为 E,即只能是 E 或者 E 的子类
        // <? super E>,集合中元素类型下限为 E,即只能是 E 或者 E 的父类
        //Comparable<? super E>表示实现了Comparable接口的类,且这个接口中T是E本身或父类。
        Comparable<? super E> key = (Comparable<? super E>) x;
        while (k > 0) {
            int parent = (k - 1) >>> 1;      //获取k的父节点。
            Object e = queue[parent];      //取得父节点
            if (key.compareTo((E) e) >= 0)    //如果父节点和插入值相比,插入值大于等于父节点的值。
                break;   //说明不需要上移了
            queue[k] = e;      //如果父节点值大于插入值,则父节点交换到当前k,即当前比较的父节点的子节点位置
            k = parent;    //更新k位置原先父节点位置,进行下一次判断。即代表插入的节点本次循环上移到该位置。
        }
        queue[k] = key;     //找到插入值需要上移到的位置后,将数组中对应位置,赋值为插入元素的值。
    }

    @SuppressWarnings("unchecked")
    private void siftUpUsingComparator(int k, E x) {//使用了比较器的上移插入元素的版本
        while (k > 0) {
            int parent = (k - 1) >>> 1;         //获取k的父节点。
            Object e = queue[parent];    //获取父节点值
            if (comparator.compare(x, (E) e) >= 0)  //如果插入值大于等于父节点的值。
                break;  //上移完毕
            queue[k] = e;     //否则,将父节点下移到当前的k位置,即当前比较父节点的子节点位置,
            k = parent;    //更新k位置原先父节点位置,进行下一次判断。即代表插入的节点本次循环上移到该位置。
        }
        queue[k] = x;//找到插入值需要上移到的位置后,将数组中对应位置,赋值为插入元素的值。
    }

(2)siftDown 方法用于在指定位置插入指定元素,然后向下调整 x (和其子节点进行比较)直到满足堆成立的条件。在poll方法中,下移的是队列末尾的元素。
原理如下:
java集合 PriorityQueue原理, 通过源码学习进行深入了解
当一个元素插入到队列头时,需要将其下移,以满足最小堆的结构。siftDown方法就是实现在指定位置k,插入元素后,进行下移维护堆结构。
siftDown的实现原理:
首先是获取当前位置的左子节点:child= (k<<1)+1,
再获得右子节点:right = (k<<1)+2;
取得c为左右节点中值最小的那一个,如果左右子节点相等,则赋值为左子节点。
使用c与当前k位置上的值key(也就是传入的x)作比较,如果key>c,则需要下移
下移就是就是将左右子节点中大的那个值交换到当前父节点,queue[k]=c。
而后k更新为左右子节点中大的那个的索引,下一轮循环将和当前值偏小的那个子节点的左右子节点比较。
直到满足,当前插入的值小于等于本次循环的左右子节点的最小值。那么停止循环,这时已经不需要下移了。而注意,任何时候这个k,要保证大于size的一半,因为只有下移到非叶子节点,才会需要继续判断。
源码实现如下:
注意:根据是否指定了比较器,分为两个siftUp方法,而这两个方法原理相同,只是比较时代码略有不同

    /**
     * Inserts item x at position k, maintaining heap invariant by
     * demoting x down the tree repeatedly until it is less than or
     * equal to its children or is a leaf.
     * 在 k 位置插入元素 x,通过向下调整 x 直到它小于等于它的子节点或者
     *   叶节点,来保证满足堆成立的条件。
     * @param k the position to fill
     * @param x the item to insert
     */
    private void siftDown(int k, E x) {   //向下调整插入的元素
        if (comparator != null)
            siftDownUsingComparator(k, x);  //使用Comparator比较器方法
        else
            siftDownComparable(k, x);       //元素本身是实现了Comparable
    }

    @SuppressWarnings("unchecked")
    //传入的是,初始插入位置为k,值为x的元素
    private void siftDownComparable(int k, E x) {   //元素本身实现了Comparable
        Comparable<? super E> key = (Comparable<? super E>)x;    //转化为实现了Comparable接口的类,且接口是E及E的父类的
        int half = size >>> 1;        //    //得到队列中间一半的位置索引
        //如果k小于中间位置索引,则循环,因为叶堆的叶子节点索引大于中间的索引。
        //即只要k,为非叶子节点,就循环。
        while (k < half) {
            int child = (k << 1) + 1; // assume left child is least  //得到k位置的孩子左子节点索引,
            Object c = queue[child];   //取得左子节点值
            int right = child + 1;   //取得右子节点的索引,
            if (right < size &&         //如果有右子节点
                    ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0) //比较,如果右子节点值小于左子节点
                c = queue[child = right];    //则c赋值为右子节点,即c会赋值为,左右子节点中较小的数,如果左右相等,取左子节点。
            //使用左右子节点最大的值和传入的元素值进行比较,
            //因为下移,所以直到元素值小于等于当前左右子节点中最小值,说明不需要下移了。
            if (key.compareTo((E) c) <= 0)
                break;
            queue[k] = c;       //如果不满足,则将较小的孩子节点,交换到其父节点位置,即当前的k位置。
            k = child;              //k更新为较小的孩子节点的位置,方便下次判断。
        }
        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)  //比较时使用this.comparator.compare方法比较。
                c = queue[child = right];  //c赋值为较小的孩子节点值
            if (comparator.compare(x, (E) c) <= 0)    //直到插入的节点大于等于当前左右子节点最小值
                break;      //结束下移
            queue[k] = c;
            k = child;
        }
        queue[k] = x;
    }

heapify 和 removeAt

(1)heapify
将整个堆进行最小堆调整,思想就是从非叶子节点开始进行下移操作,倒序操作说明方法建立最小堆/最大堆是从下到上的。即先让最底层符合最小堆/最大堆结构然后保证上层的下移操作交换的都是当前其子堆中最小/最大的值。只要这样遍历到队列头,每一次都进行下移操作即可实现将整个队列变为优先队列
即建立起最小堆/最大堆。

  /**
     * Establishes the heap invariant (described above) in the entire tree,
     * assuming nothing about the order of the elements prior to the call.
     * 在整个树中建立堆不变量(如上所述),
     *
     * 不假设调用之前元素的顺序。
     */
    @SuppressWarnings("unchecked")
    //将整个堆进行最小堆调整,思想就是从非叶子节点开始进行下移操作
    //倒序操作,说明方法建立最小堆/最大堆是从下到上的。即先让最底层符合最小堆/最大堆结构
    //然后保证上层的下移操作交换的都是当前其子堆中最小/最大的值。
    //只要这样遍历到队列头,每一次都进行下移操作即可实现将整个队列变为优先队列
    //即建立起最小堆/最大堆。
    private void heapify() {
        for (int i = (size >>> 1) - 1; i >= 0; i--) //即从队列中间位置开始遍历
            siftDown(i, (E) queue[i]);       //逐个进行下移操作,
    }

(2)removeAt
在优先队列的头和尾部插入,只需要下移和上移操作,而在指定位置删除后,会把队列最后一个元素插入到删除的这个位置上,而这时候,有可能需要上移,也有可能需要下移。因为最小堆的左右子树无法保证大于还是小于的情况。
所以removeAt首先调用siftDown(i, moved),如果发现,这时queue[i]==moved还是成立,说明没有发生下移,则还需要调用siftUp(i, moved)上移操作,如果发现queue[i] != moved,即至少发生了一次上移,
说明队列后的元素,跑到了i索引前,这样迭代器的遍历就无法遍历到这个值了,所以这时removeAt返回moved,让迭代器iterator.remove方法调用此方法后,判断返回值如果不为null,即将这个值将入到丢失队列中。如果插入末尾元素,未发生上移操作,则返回null,让迭代器知道没有发生数据丢失,那迭代器就正常迭代。

  /**
     * Removes the ith element from queue.
     *从队列中删除第 i 个元素。
     * Normally this method leaves the elements at up to i-1,
     * inclusive, untouched.  Under these circumstances, it returns
     * null.  Occasionally, in order to maintain the heap invariant,
     * it must swap a later element of the list with one earlier than
     * i.  Under these circumstances, this method returns the element
     * that was previously at the end of the list and is now at some
     * position before i. This fact is used by iterator.remove so as to
     * avoid missing traversing elements.
     * 即删除一个值,就是将队列最后一个元素,提到这个i位置上
     * 然后先进行下移操作,因为下移操作只会将这个元素移到i后面的索引,
     * 并且后面索引上的值也只会移到i包括i后面,这些元素在迭代器遍历是,都不回丢失
     * 索引如果只是下移操作,直接返回null。
     * 但是如果下移操作没有执行,即queue[i]==moved,则说明应该进行上移判断
     * 如果发生了一次上移操作,说明这个原来在索引i后的元素,移动到了索引i之前,
     * 那么迭代器遍历就会缺失这个元素,所以要返回moved进行额外保存。
     */
    @SuppressWarnings("unchecked")
    private E removeAt(int i) {
        // assert i >= 0 && i < size; 断言,i肯定满足合法性
        modCount++;
        int s = --size;   //size更新后,赋值给s
        if (s == i) // removed last element //如果i==s,说明是最后一个元素的索引
            queue[i] = null;     //直接令最后一个元素为null。
        else {
            E moved = (E) queue[s];             //先保存队列最后一个元素值。
            queue[s] = null;          //将最后一个位置赋值为null。
            siftDown(i, moved);  //将最后这个值插入到当前删除位置的地方,并进行堆下移操作。
            // 如果没有向下调整,说明可能它的位置在上面,接着向上调整
            if (queue[i] == moved) {   //当前i上的值还是下移前保存的值,说明没有进行下移
                siftUp(i, moved);      //则进行上移
                if (queue[i] != moved)      //如果当前i不等于上移前保存的值,说明至少上移了一次。
                    return moved;      //返回原队列末尾的值
            }
        }
        return null;  //否则返回null。
    }

add 和 offer

这两个方法原理相同,先检查插入值是否为null,再检查是否需要扩容。
如果不是第一次添加,即添加后队列不止一个元素,则需要调用siftUp进行上移。
原理见上面siftUp方法

 /**
     * Inserts the specified element into this priority queue.
     *将指定元素插入到优先级队列中
     * @return {@code true} (as specified by {@link Collection#add})
     * @throws ClassCastException if the specified element cannot be
     *         compared with elements currently in this priority queue
     *         according to the priority queue's ordering
     * @throws NullPointerException if the specified element is null
     */
    public boolean add(E e) {
        return offer(e);
    }

    /**
     * Inserts the specified element into this priority queue.
     *将指定元素插入到优先级队列中
     * @return {@code true} (as specified by {@link Queue#offer})
     * @throws ClassCastException if the specified element cannot be
     *         compared with elements currently in this priority queue
     *         according to the priority queue's ordering
     * @throws NullPointerException if the specified element is null
     */
    public boolean offer(E e) {
        if (e == null)    //为null会抛出空指针异常
            throw new NullPointerException();
        modCount++;
        int i = size;
        if (i >= queue.length)   //判断是否需要扩容
            grow(i + 1);
        size = i + 1;  //更新size
        if (i == 0)     //如果是第一次添加元素,
            queue[0] = e;
        else       //不是第一次,需要调用siftUp进行添加,因为需要维护堆的结构
            siftUp(i, e);
        return true;
    }

element 和 peek

原理如下:
java集合 PriorityQueue原理, 通过源码学习进行深入了解
返回数组中第一个元素值,即堆顶。
element 实际上使用的是子类AbstractQueue中的方法

 public E element() {
        E x = peek();
        if (x != null)
            return x;
        else
            throw new NoSuchElementException();
    }

peek在priorityqueue中定义为:

 @SuppressWarnings("unchecked")
    public E peek() {   //取得队列头部元素,队列为空返回null
        return (size == 0) ? null : (E) queue[0];
    }

remove 和 poll

:这两个方法原理相同,删除队列头部元素,并返回这个值,删除后,即将队列末尾的值填充到队首,然后进行siftDown下移操作。
原理见上面siftDown方法
remove 实际上使用的是子类AbstractQueue中的方法

 public E remove() {
        E x = poll();
        if (x != null)
            return x;
        else
            throw new NoSuchElementException();
    }

poll在priorityqueue中定义为:

 @SuppressWarnings("unchecked")
    //实际上就是取出队首元素,即堆顶元素,然后用最后一个队列元素填充
    //然后在进行下移操作,因为放到了队首,只可能进行siftDown操作。
    public E poll() {           //弹出队列头部元素,队列为空返回null。
        if (size == 0)
            return null;
        int s = --size;        //size自减,并取得最后一个元素的值
        modCount++;
        E result = (E) queue[0];         //保存队列头部元素值,用于返回
        E x = (E) queue[s];                //保存队尾元素值,用于比较
        queue[s] = null;      //队列为空赋值为null。
        if (s != 0)           //只要原先队列不止一个元素,
            siftDown(0, x);       //就从0队首位置开始进行下移操作。
        return result;     //返回堆顶值
    }

PriorityQueue 小结

  • 扩容机制和线性数据结构的机制基本相似,一般情况下扩容为 1.5 * oldCapacity 或者 2 * oldCapacity + 2。

  • 队列里不允许 null 元素。

  • 底层数据结构是存储在使用数组实现的堆,插入删除操作依赖堆的调整函数 siftUp 和 siftDown,对于不同的比较器,堆的调整过程中的判断条件也不同。

参考:

https://www.cnblogs.com/Elliott-Su-Faith-change-our-life/p/7472265.html
https://github.com/Augustvic/JavaSourceCodeAnalysis/blob/master/md/Collections/PriorityQueue.md

本文地址:https://blog.csdn.net/qq_30921153/article/details/107380351