PriorityQueue源码分析

一、概述

PriorityQueue直接翻译就是一个优先队列，获取数据的时候会按照一定优先级（排序）；

二、PriorityQueue的对象模型

            
                     PriorityQueue   
                   /                 \        
            exetend                     implements
        AbstractQueue                     Serializable
        /          \       
  exetned         implements
AbstractCollection    Queue 
        \           /
    implements    exetned
          Collection
              |
           extends
           Iterable

                                                                  画的不好，请见谅

PriorityQueue实现了Queue的AbstractQueue抽象类，集成Queue 的方法
新增删除获取

add remove peek

offer poll element

poll

add和remove会根据是否抛异常判断成功

offer和poll会根据返回值判断是否成功

新增	删除	获取
add	remove	peek
offer	poll	element
		poll

三、PriorityQueue的源码

参数对象

private static final int DEFAULT_INITIAL_CAPACITY = 11;//默认初始容量11
transient Object[] queue; // 一个不会被序列化的队列
private int size = 0;//队列元素个数
private final Comparator<? super E> comparator;//判断队列优先的比较器
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) {
        }
//放入一个SortedSet，PriorityQueue，或其他集合，继承（SortedSet，PriorityQueue）的比较器
//将其元素插入queue，将其长度作为初始化容量
public PriorityQueue(Collection<? extends E> c) {...}
//大致同上
public PriorityQueue(PriorityQueue<? extends E> c) {...}
//大致同上
public PriorityQueue(SortedSet<? extends E> c) {...}

我们不难看出，构造方法关键的参数为比较器，容量，还可以通过一个集合来实现。

如果没有传递比较器参数，默认的比较器他是这么叙述的

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.//比较器使用这个比较器作为优先队列的依据，如果没有比较器，那么就用自然排序

如果没有size，那么默认是DEFAULT_INITIAL_CAPACITY = 11

对象操作API

新增方法

public boolean add(E e) {
        return offer(e);//add方法直接调用了offer方法，可以看做是同一个方法
    }
public boolean offer(E e) {
        if (e == null)//不允许控制的入队
            throw new NullPointerException();
        modCount++;//修改次数
        int i = size;
        if (i >= queue.length)//增加容量
            grow(i + 1);
        size = i + 1;//插入容量对象
        if (i == 0)//如果是第一个元素
            queue[0] = e;
        else//否则插入到队尾
            siftUp(i, e);
        return true;
   }

删除方法

public boolean remove(Object o) {
        int i = indexOf(o);//查询删除对象的索引，一个O(n)的时间复杂度
        if (i == -1)//如果是-1说明不存在
            return false;
        else {
            removeAt(i);//调用删除方法
            return true;
        }
    }
private int indexOf(Object o) {
        if (o != null) {//判断非空后循环匹配，一个O(n)的时间复杂度
            for (int i = 0; i < size; i++)
                if (o.equals(queue[i]))
                    return i;
        }
        return -1;
    }
 private E removeAt(int i) {
        // assert i >= 0 && i < size;
        modCount++;//操作次数+1
        int s = --size;//容量-1
        if (s == i) // 如果是last，则直接删除最后的元素
            queue[i] = null;
        else {
            E moved = (E) queue[s];
            queue[s] = null;//将last位置设置为null
            siftDown(i, moved);//将原本last的值设置到需要删除的位置，然后逐层比较替换左右孩子节点，直到小于或等于左右孩子节点其中的一个
            if (queue[i] == moved) {//如果迁移成功却没有变换堆结构
                siftUp(i, moved);//将待变换节点向上比较替换，直到大于或等于左右孩子其中的一个
                if (queue[i] != moved)
                    return moved;//作为迭代器返回
            }
        }
        return null;
    }

未完待续。。。。。。。。。。。。。。。。。。。。。。。。。。