PriorityQueue源碼分析

一、概述

PriorityQueue直接翻譯就是一個優(yōu)先隊列笋颤，獲取數(shù)據(jù)的時候會按照一定優(yōu)先級（排序）钓简；

二油啤、PriorityQueue的對象模型

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

                                                                  畫的不好亿胸，請見諒

PriorityQueue實現(xiàn)了Queue的AbstractQueue抽象類坯钦，集成Queue 的方法
新增刪除獲取

add remove peek

offer poll element

poll

add和remove會根據(jù)是否拋異常判斷成功

offer和poll會根據(jù)返回值判斷是否成功

新增	刪除	獲取
add	remove	peek
offer	poll	element
		poll

三法严、PriorityQueue的源碼

參數(shù)對象

private static final int DEFAULT_INITIAL_CAPACITY = 11;//默認(rèn)初始容量11
transient Object[] queue; // 一個不會被序列化的隊列
private int size = 0;//隊列元素個數(shù)
private final Comparator<? super E> comparator;//判斷隊列優(yōu)先的比較器
transient int modCount = 0; // 老規(guī)矩，修改的次數(shù)（增刪改）

構(gòu)造方法

//無參的構(gòu)造方法葫笼，使用了默認(rèn)的長度進(jìn)行初始化
public PriorityQueue() {
        this(DEFAULT_INITIAL_CAPACITY, null);
        }
//帶有長度參數(shù)的構(gòu)造方法
public PriorityQueue(int initialCapacity) {
        this(initialCapacity, null);
        }
//帶有比較器的構(gòu)造方法
public PriorityQueue(Comparator<? super E> comparator) {
        this(DEFAULT_INITIAL_CAPACITY, comparator);
        }
//帶有長度和比較器的構(gòu)造方法
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) {...}

我們不難看出洋丐，構(gòu)造方法關(guān)鍵的參數(shù)為比較器，容量挥等，還可以通過一個集合來實現(xiàn)友绝。

如果沒有傳遞比較器參數(shù)，默認(rèn)的比較器他是這么敘述的

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.//比較器使用這個比較器作為優(yōu)先隊列的依據(jù)肝劲，如果沒有比較器迁客，那么就用自然排序

如果沒有size，那么默認(rèn)是DEFAULT_INITIAL_CAPACITY = 11

對象操作API

新增方法

public boolean add(E e) {
        return offer(e);//add方法直接調(diào)用了offer方法辞槐，可以看做是同一個方法
    }
public boolean offer(E e) {
        if (e == null)//不允許控制的入隊
            throw new NullPointerException();
        modCount++;//修改次數(shù)
        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)的時間復(fù)雜度
        if (i == -1)//如果是-1說明不存在
            return false;
        else {
            removeAt(i);//調(diào)用刪除方法
            return true;
        }
    }
private int indexOf(Object o) {
        if (o != null) {//判斷非空后循環(huán)匹配，一個O(n)的時間復(fù)雜度
            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++;//操作次數(shù)+1
        int s = --size;//容量-1
        if (s == i) // 如果是last榄檬，則直接刪除最后的元素
            queue[i] = null;
        else {
            E moved = (E) queue[s];
            queue[s] = null;//將last位置設(shè)置為null
            siftDown(i, moved);//將原本last的值設(shè)置到需要刪除的位置卜范，然后逐層比較替換左右孩子節(jié)點，直到小于或等于左右孩子節(jié)點其中的一個
            if (queue[i] == moved) {//如果遷移成功卻沒有變換堆結(jié)構(gòu)
                siftUp(i, moved);//將待變換節(jié)點向上比較替換鹿榜，直到大于或等于左右孩子其中的一個
                if (queue[i] != moved)
                    return moved;//作為迭代器返回
            }
        }
        return null;
    }

未完待續(xù)海雪。。舱殿。奥裸。。怀薛。刺彩。。枝恋。创倔。。焚碌。畦攘。。十电。知押。叹螟。。台盯。罢绽。。静盅。良价。。蒿叠。明垢。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者