PriorityQueue的介紹

PriorityQueue也叫優先隊列，所謂的優先隊列其實就是每次從優先隊列中取出來的元素要么是最大值，要么是最小值，PriorityQueue是用二叉堆數據結構實現的。

在了解PriorityQueue之前，我們最好先吧二叉堆先了解清楚。
可以參考這篇文章：二叉堆 圖文解析。

PriorityQueue的uml圖：

說明：

PriorityQueue繼承于AbstractQueue。

PriorityQueue內部是通過Object[]數組來保存數據的，也就是說它本質是通過數組來實現的。

PriorityQueue的源碼分析

構造方法

PriorityQueue(),PriorityQueue(int),PriorityQueue(Comparetor)實際上都是使用PriorityQueue(int，Comparetor)

public PriorityQueue(int initialCapacity,Comparator<? super E> comparator) {if (initialCapacity < 1)throw new IllegalArgumentException();this.queue = new Object[initialCapacity];this.comparator = comparator;}

說明：PriorityQueue的構造方法指定隊列的大小和比較器，默認的大小是DEFAULT_INITIAL_CAPACITY = 11

還有三個構造方法：
PriorityQueue(Collection< ? extends E > c)，
PriorityQueue(PriorityQueue< ? extends E> c )，
PriorityQueue(SortedSet< ? extends E > c)

我們知道SortedSet，PriorityQueue是Collection的子接口和實現，所以我們只需要了解 PriorityQueue(Collection< ? extends E> c )構造方法。

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);}}

很容易理解，它分參數c的三種情況進行處理：SortedSet，PriorityQueue和Collection

如果是PriorityQueue的話 調用initFromPriorityQueue：

private void initFromPriorityQueue(PriorityQueue<? extends E> c) {if (c.getClass() == PriorityQueue.class) {this.queue = c.toArray();this.size = c.size();} else {initFromCollection(c);}}

說明：直接把數組和大小復制過來。

如果是SortSet的話 調用initElementsFromCollection：

private void initElementsFromCollection(Collection<? extends E> c) {Object[] a = c.toArray();// If c.toArray incorrectly doesn't return Object[], copy it.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++)if (a[i] == null)throw new NullPointerException();this.queue = a;this.size = a.length;}

說明：因為是SortSet也是排序的，所以一樣復制就可以了，區別是SortSet中的元素不一定是Object[]，所以需要通過Arrays.copyOf(a, a.length, Object[].class)將元素轉成Object[]

如果是Collection的話 調用initFromCollection：

private void initFromCollection(Collection<? extends E> c) {initElementsFromCollection(c);heapify();}

說明，先調用SortSet情況下的初始化方法，然后進行堆排序，下面講解一下如何堆排序：

heapify()

//從插入最后一個元素的父節點位置開始建堆 private void heapify() {for (int i = (size >>> 1) - 1; i >= 0; i--)siftDown(i, (E) queue[i]); }

siftDown方法

//在位置k插入元素x，為了保持最小堆的性質會不斷調整節點位置 private void siftDown(int k, E x) {if (comparator != null)//使用插入元素的實現的比較器調整節點位置siftDownUsingComparator(k, x);else//使用默認的比較器（按照自然排序規則）調整節點的位置siftDownComparable(k, x); }

這里只演示默認比較器的情況，自定義比較器其實差不多。

//具體實現調整節點位置的函數 private void siftDownComparable(int k, E x) {Comparable<? super E> key = (Comparable<? super E>)x;// 計算非葉子節點元素的最大位置int half = size >>> 1; // loop while a non-leaf//如果不是葉子節點則一直循環while (k < half) {//得到k位置節點左孩子節點，假設左孩子比右孩子更小int child = (k << 1) + 1; // assume left child is least//保存左孩子節點值Object c = queue[child];//右孩子節點的位置int right = child + 1;//把左右孩子中的較小值保存在變量c中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;}//循環結束，k是葉子節點queue[k] = key; }

說明，這個函數是調整某個節點的位置，方法是，從這個節點A開始，跟它的兩個子節點中最小一個B比較，如果該節點A更小則方法結束，如果B更小，則把B和A的位置互換，然后把這個字節點當成“當前節點”往下遞歸。

添加元素

public boolean add(E e) {//調用offer函數return offer(e);} public boolean offer(E e) {if (e == null)throw new NullPointerException();modCount++;int i = size;//如果size大于等于隊列的大小，就要對隊列，也就是數組擴容if (i >= queue.length)grow(i + 1);size = i + 1;if (i == 0)queue[0] = e;else//具體執行添加元素的函數siftUp(i, e);return true;} //調用不同的比較器調整元素的位置 private void siftUp(int k, E x) {if (comparator != null)siftUpUsingComparator(k, x);elsesiftUpComparable(k, x); } //使用默認的比較器調整元素的位置 private void siftUpComparable(int k, E x) {Comparable<? super E> key = (Comparable<? super E>) x;while (k > 0) {int parent = (k - 1) >>> 1;//保存父節點的值Object e = queue[parent];//使用compareTo方法，如果要插入的元素小于父節點的位置則交換兩個節點的位置if (key.compareTo((E) e) >= 0)break;queue[k] = e;k = parent;}queue[k] = key; }

可以從代碼中看出來，添加一個元素是首先吧元素添加到最后，然后跟父節點對比，如果比父節點小，就互換位置，相當于它“上移”了，然后再往上比較。

刪除元素

remove方法

private E removeAt(int i) {assert i >= 0 && i < size;modCount++;//s是隊列的隊頭，對應到數組中就是最后一個元素int s = --size;//如果要移除的位置是最后一個位置，則把最后一個元素設為nullif (s == i) // removed last elementqueue[i] = null;else {//保存待刪除的節點元素E moved = (E) queue[s];queue[s] = null;//先把最后一個元素和i位置的元素交換，之后執行下調方法siftDown(i, moved);//如果執行下調方法后位置沒變，說明該元素是該子樹的最小元素，需要執行上調方//法,保持最小堆的性質if (queue[i] == moved) {//位置沒變siftUp(i, moved); //執行上調方法if (queue[i] != moved)//如果上調后i位置發生改變則返回該元素return moved;}}return null; }

在上面的代碼上調方法與下調方法只會執行其中的一個，參看下面例子

需要執行下調方法的示意圖：

這是需要執行上調方法的示意圖：

擴容操作

在添加元素中有個grow擴容操作，下面我們對它進行解析：

private void grow(int minCapacity) {int oldCapacity = queue.length;// 如果舊容量小擴大為原來2倍，否則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);}private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflowthrow new OutOfMemoryError();return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;}

總結：

• 時間復雜度：remove()方法和add()方法時間復雜度為O(logn)，remove(Object obj)和contains()方法需要O(n)時間復雜度，取隊頭則需要O(1)時間

• 在初始化階段會執行建堆函數，最終建立的是最小堆，每次出隊和入隊操作不能保證隊列元素的有序性，只能保證隊頭元素和新插入元素的有序性，如果需要有序輸出隊列中的元素，則只要調用Arrays.sort()方法即可

• PriorityQueue是非同步的，要實現同步需要調用java.util.concurrent包下的PriorityBlockingQueue類來實現同步

• 在隊列中不允許使用null元素

總結

以上是生活随笔為你收集整理的容器源码分析之PriorityQueue(十)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。