PriorityQueue源码分析

女爷i 2023-01-19 10:57 14阅读 0赞

**阅读本文章之前推荐先阅读博主关于堆排序相关的内容，传送地址：[八大排序算法大汇总 原理+图解+源码+复杂度分析][Link 1]**

# PriorityQueue源码分析 #

### 文章目录 ###

*  PriorityQueue源码分析
 *   *  一、堆结构
     *  二、基本介绍
     *  三、源码分析
     *   *  1. 主要属性
         *  2. 构造方法
         *  3. 入队方法
         *   *  3.1 add方法
             *  3.2 offer方法
         *  4. 扩容方法
         *  5. 出队方法
         *   *  5.1 remove()方法
             *  5.2 poll()方法
         *  6. 删除方法
         *   *  6.1 remove(Object o)方法
         *  7. 查看队首元素方法
         *   *  7.1 element()方法
             *  7.2 peek()方法
     *  四 、总结

## 一、堆结构 ##

1.  满二叉树：所有层都达到最大节点数的二叉树
    
    ![image-20210425233955040][]
2.  完全二叉树：所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，称为完全二叉树，也就是说添加结点时需要把每一层从左往右填满之后才可在下一层从左往右添加结点
    
    通俗的理解为：完全二叉树是指除了最后一层外其它层都达到最大节点数，且最后一层节点都靠左排列
    
    ![img][]
    
    左孩子结点的索引：2 \* 当前节点的索引 + 1
    
    右孩子结点的索引：2 \* 当前结点的索引 + 2
    
    父节点的索引：(当前结点的索引 - 1) / 2
    
    结点数为n，则层数为logn (父与子结点的索引关系以2倍为基础)
3.  堆：就是一颗完全二叉树
4.  大顶堆：每个结点的值都大于或等于其左右孩子结点的值，没有要求左右孩子结点的大小关系，堆顶是最大值
5.  小顶堆：每个节点的值都小于或等于其左右孩子结点的值，没有要求左右孩子结点的大小关系，堆顶是最小值
6.  一个长度为size的堆结构，如果一个节点的索引值index大于等于 `size >>> 1` 时，认为该节点为叶子节点，否则就是非叶子节点
7.  优先级队列就是堆结构，Java中无Heap类表示堆结构，使用PriorityQueue类表示堆结构：
    
    (1) 此类支持泛型
    
    (2) 此类的构造器参数中可以传递一个实现了Comparator接口的类，表示往堆中添加元素时按照此类的compare方法中的排序方式加入；注意：优先级队列默认是小顶堆

## 二、基本介绍 ##

*  优先级队列，是0个或多个元素的集合，集合中的每个元素都有一个权重值，每次出队都弹出权重值最大或最小的元素
 *  优先级队列使用堆来实现，默认是小顶堆
 *  不可以添加取值为null的元素
 *  PriorityQueue是非线程安全的
 *  PriorityQueue不是有序的，只有堆顶存储着最小或最大的元素
 *  继承体系
    
    Queue 的实现类有 ArrayDeque、LinkedList、PriorityQueue
    
    ![image-20210426091929910][]
 *  Queue 接口中定义了如下方法：
    
    ![image-20210426101914933][]
    
    PriorityQueue 中也实现了这些方法

## 三、源码分析 ##

### 1. 主要属性 ###

//默认容量
    private static final int DEFAULT_INITIAL_CAPACITY = 11;
    
    //存储元素的地方
    transient Object[] queue;
    
    //实际元素个数
    int size;
    
    //比较器
    private final Comparator<? super E> comparator;
    
    //修改次数
    transient int modCount;

观察上述属性可得到如下结论：

*  优先级队列的默认容量是11
 *  实际存储元素的结构是Object类型的数组（堆一般使用数组来存储）
 *  在优先级队列中，有两种方式比较元素的大小，一种是元素的自然顺序（默认为小顶堆），另一种是通过比较器比较
    
     *  如果使用默认方式，要求添加的元素必须实现Comparable接口
 *  拥有 `modCount` 属性，表示优先级队列有快速失败的特性

### 2. 构造方法 ###

常用的构造方法如下所示：

//空参构造器，使用默认的长度为11的容量，没有定义比较器
    public PriorityQueue() { 
        this(DEFAULT_INITIAL_CAPACITY, null); 
    }
    
    //指定初始容量的构造器，没有定义比较器
    public PriorityQueue(int initialCapacity) { 
        this(initialCapacity, null);
    }
    
    //指定比较器，且使用默认容量11的构造器
    public PriorityQueue(Comparator<? super E> comparator) { 
        this(DEFAULT_INITIAL_CAPACITY, comparator);
    }
    
    //指定初始容量及比较器的构造器
    public PriorityQueue(int initialCapacity,
                         Comparator<? super E> comparator) { 
        if (initialCapacity < 1)
            throw new IllegalArgumentException();
        this.queue = new Object[initialCapacity];
        this.comparator = comparator;
    }
    
    //指定集合的构造器
    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 { 
            this.comparator = null;
            initFromCollection(c);
            //没有指定比较器，从参数集合中初始化队列元素后调整成为小顶堆
        }
    }

### 3. 入队方法 ###

#### 3.1 add方法 ####

`add(E e)` 源码如下：

public boolean add(E e) { 
        return offer(e); //调用offer方法
    }

#### 3.2 offer方法 ####

`offer(E e)` 源码如下：

public boolean offer(E e) { 
        if (e == null)
            throw new NullPointerException(); //不支持null元素
        
        modCount++;
        int i = size; //i的值比最后一个元素的索引值大1，也就是待插入位置的索引
        
        //元素个数超过了队列的最大容量，调用grow方法扩容
        if (i >= queue.length)
            grow(i + 1); //扩容方法之后讲述
        
        //调用siftUp方法，将元素添加到队列尾部并重新调整成为小顶堆（默认情况下）
        siftUp(i, e);
        
        size = i + 1;
        return true;
    }

`siftUp(int k, E x)` 方法源码如下：

//k表示待插入位置的索引，x表示待插入元素
    private void siftUp(int k, E x) { 
        
        //根据是否有比较器而调用不同的方法
        
        if (comparator != null)
            siftUpUsingComparator(k, x, queue, comparator);
        else
            siftUpComparable(k, x, queue);
    }

`siftUpComparable(int k, T x, Object[] es)` 方法源码如下：

/** * 参数k表示size，比当前最后一个元素的索引值大1，即待插入位置的索引 * 参数x表示要添加到队尾的元素 * 参数es表示存储元素的数组 */
    private static <T> void siftUpComparable(int k, T x, Object[] es) { 
        Comparable<? super T> key = (Comparable<? super T>) x; //key表示要添加的元素
        
        //如果k==0，即堆为空时，不进入while循环，直接将元素赋予数组首位置
        while (k > 0) { 
            
            //元素将要添加的位置就是size，即k
            
            //找到父节点的索引
            int parent = (k - 1) >>> 1;
            
            //e表示父节点的值
            Object e = es[parent];
            
            //如果要添加元素的值大于父节点的值，则跳出循环，已经满足小顶堆的要求
            if (key.compareTo((T) e) >= 0)
                break;
            
            //如果比父节点的值小，则需要与父节点交换位置，其实就是将父节点移动到了原本属于此元素的位置
            es[k] = e;
            
            //新插入的元素成为父节点，继续执行循环与父节点比较
            k = parent;
        }
        //找到该插入的位置，将元素插入
        es[k] = key;
    }

观察上述源码，可以得到如下结论：

*  不允许添加null元素
 *  如果数组不够用了，先扩容
 *  如果堆中还没有元素，新添加的元素成为首元素
 *  如果堆中已经有元素了，就插入到最后一个元素往后的一个位置（此时还没有实际插入）并重新调整成为小顶堆（持续与父节点比较，找到合适的位置再将元素实际插入）
 *  为什么PriorityQueue中的add(e)方法没有做异常检查呢？
    
     *  因为PriorityQueue是无限增长的队列，元素不够用了会扩容，所以添加元素不会失败

### 4. 扩容方法 ###

`grow(int minCapacity)` 方法源码如下：

//参数minCapacity的取值为扩容之前的size + 1
    private void grow(int minCapacity) { 
        int oldCapacity = queue.length;
        
        //如果旧容量小于64，新容量为旧容量的2倍+2
        //如果旧容量大于等于64，新容量为旧容量的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);
    }

`hugeCapacity(minCapacity)` 方法源码如下：

private static int hugeCapacity(int minCapacity) { 
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
    }

### 5. 出队方法 ###

#### 5.1 remove()方法 ####

`remove()` 方法存在于AbstractQueue类中，弹出队首的元素，源码如下：

public E remove() {     E x = poll(); //调用poll方法移除队首的元素 if (x != null) return x; else throw new NoSuchElementException(); //如果没有队首元素，则抛出异常}

#### 5.2 poll()方法 ####

`poll()` 方法源码如下，弹出队首的元素：

思路：首先将数组最后一个元素的值保存起来（假设保存在x中），对最后一个元素赋予null值（相当于长度减一），使用x从首元素的子节点开始比较，有两种情况：

*  如果x小于两个子节点，已满足小顶堆的要求，则x成为父节点，此时原首元素被覆盖
 *  如果子节点有比x小的，此子节点成为父节点，此时原首元素被覆盖；x成为子节点继续向下比较，直到找到合适的位置插入

public E poll() { 
        final Object[] es;
        final E result;
    
        //当队列不为空时执行if语句
        if ((result = (E) ((es = queue)[0])) != null) { 
            
            //es表示存储元素的数组
            //result表示队首元素，一开始就保存起来，所以即使后期首元素被覆盖也可以返回原首元素
            
            modCount++;
            final int n;
            final E x = (E) es[(n = --size)];  
            //n表示size-1，即最后一个元素的索引
            //x表示数组最后一个元素
            
            es[n] = null; //将最后一个元素清空
            
            //若队列中有两个元素及以上时才执行if
            if (n > 0) { 
                
                //根据是否定义比较器从而调用不同的方法
                
                final Comparator<? super E> cmp;
                if ((cmp = comparator) == null)
                    siftDownComparable(0, x, es, n);
                else
                    siftDownUsingComparator(0, x, es, n, cmp);
                	//过程与siftDownComparable方法类似，不再赘述，唯一的区别是比较时使用的是传递进来的Comparator比较器中的compare方法
            }
        }
        return result; //返回队首元素，若没有队首元素不抛异常，返回null
    }

`siftDownComparable()` 方法源码如下：

/** * 参数k取值为0，队首索引，也就是将要被删除的元素的索引 * 参数x表示数组最后一个元素，在最后一个元素被赋予null值之前已将其保存至x * 参数es表示存储元素的数组 * 参数n表示size-1 */
    //此时数组的最后一个元素为null，但原来最后一个元素的值被赋予null值之前已将其保存至x
    private static <T> void siftDownComparable(int k, T x, Object[] es, int n) { 
        Comparable<? super T> key = (Comparable<? super T>)x;
        int half = n >>> 1; //用于保证是非叶子节点
        
        //仅与非叶子节点比较
        while (k < half) { 
            int child = (k << 1) + 1; //child左孩子节点索引值
            Object c = es[child]; //c表示左孩子节点的值
            int right = child + 1; //right表示右孩子节点索引值
            
            //不越界的情况下，左右孩子节点取其小者赋予c，较小者的索引赋予child
            if (right < n &&
                ((Comparable<? super T>) c).compareTo((T) es[right]) > 0)
                c = es[child = right];
            
            //x（之前已保存的最后一个元素）如果比两个子节点的值都小，停止比较，已满足小顶堆
            if (key.compareTo((T) c) <= 0)
                break;
            
            //如果比最小的子节点大，则交换位置，较小者成为父节点
            es[k] = c;
            
            //原来的父节点移到最小子节点的位置继续往下比较
            k = child;
        }
        
        //找到正确位置放入x（之前已保存的最后一个元素）
        es[k] = key;
    }

### 6. 删除方法 ###

#### 6.1 remove(Object o)方法 ####

过程与移除队首元素类似，不同之处在于最后一个元素不是从根节点的子节点开始比较，而是从待删除元素的子节点开始比较

`remove(Object o)` 源码如下：

public boolean remove(Object o) { 
        
        //调用indexOf方法得到要删除元素的索引值，若没有此元素返回-1
        int i = indexOf(o); 
        if (i == -1)
            return false; //删除失败
        else { 
            removeAt(i); //调用removeAt方法删除元素
            return true;
        }
    }

`indexOf(Object o)` 方法源码如下：

private int indexOf(Object o) { 
        if (o != null) { 
            final Object[] es = queue;
            for (int i = 0, n = size; i < n; i++)
                if (o.equals(es[i]))
                    return i;
        }
        return -1; //若没有此元素返回-1
    }

`removeAt(int i)` 源码如下：

E removeAt(int i) { 
        final Object[] es = queue;
        modCount++;
        int s = --size; //s表示size-1，即最后一个元素的索引
        
        //如果索引为最后一个元素，则删除队列最后一个元素即可
        if (s == i) 
            es[i] = null;
        
        //如果删除的不是最后一个元素
        else { 
            E moved = (E) es[s]; //moved为最后一个元素
            es[s] = null; //将队列最后一个元素置为null，相当于长度减一
            
            //调用siftDown方法，参数i表示要被删除元素的索引，moved为最后一个元素
            siftDown(i, moved);
            //执行完之后i成为最后一个元素插入的位置，moved仍然是被保存起来的最后一个元素
            
            //如果执行siftDown向下调整没有改变队列
            if (es[i] == moved) { 
                
                siftUp(i, moved); //向上调整
                //从当前节点开始与父节点比较大小，如果比父节点大，则停止比较，否则持续向上比较，直到找到合适的位置插入，过程类似于反向的siftDown，不再赘述
                
                if (es[i] != moved)
                    return moved;
            }
        }
        return null;
    }

方法源码如下：

private void siftDown(int k, E x) {         //根据是否定义比较器从而调用不同的方法 if (comparator != null) siftDownUsingComparator(k, x, queue, size, comparator); else siftDownComparable(k, x, queue, size); //此方法不再赘述}

### 7. 查看队首元素方法 ###

#### 7.1 element()方法 ####

`element()` 方法源码如下：

public E element() {     E x = peek(); //调用peek方法 if (x != null) return x; else throw new NoSuchElementException(); //没有队首元素时抛出异常}

#### 7.2 peek()方法 ####

`peek()` 方法源码如下：

public E peek() {     return (E) queue[0]; //返回队首元素，若没有队首元素不抛异常}

## 四 、总结 ##

*  入队就是堆的插入元素的实现
 *  出队就是堆的删除元素的实现

[Link 1]: https://blog.csdn.net/weixin_49343190/article/details/115286064
[image-20210425233955040]: /images/20221021/5f4b788e63494871ad656aff2c6ba0ad.png
[img]: /images/20221021/1562dc802ce647a2b0e004fe166bac8c.png
[image-20210426091929910]: /images/20221021/dca8bdbc18bd449e897c0dc88538e981.png
[image-20210426101914933]: /images/20221021/50eaedbb66b144e89225e603dd0cd4cc.png