優先級隊列PriorityQueue源碼分析

❝

掃描下方二維碼或者微信搜尋公衆号

菜鳥飛呀飛

，即可關注微信公衆号，閱讀更多

Spring源碼分析

、

Java并發程式設計

、

Netty源碼系列

和

MySQL工作原理

文章。

❞

1. 回顧

在上一篇文章中分享了堆這種資料結構，同時提到，堆可以用來對資料排序，也可以用來解決Top N、定時任務、優先級隊列等問題，今天要分享的是Java中優先級隊列PriorityQueue的源碼實作，看看堆在Java中的實際應用。需要說明的是，本文與上篇文章：「重溫《資料結構與算法》之堆與堆排序」 密切相關。

2. PriorityQueue

優先級隊列有兩個常用的操作：向隊列中添加元素、取出元素，這兩個操作的方法為「add(E e)和poll()」，接下來将圍繞這兩個方法的源碼展開。

PriorityQueue最底層采用數組來存放資料，它有很多構造方法，如果使用無參的構造方法，那麼隊列的最大容量将會采用預設值11，當一直向隊列中添加元素時，如果達到了最大容量，那麼将會進行擴容。

另外，優先級隊列中添加的元素，一定是能比較的大小的元素，而如何比較大小呢？有兩種選擇，第一：在建立PriorityQueue時「指定一個Comparator類型的比較器」；第二：添加到隊列中的元素「自身實作Comparable接口」。使用無參構造方法時，優先級隊列内部的比較器為null，是以在這種情況下，添加到隊列中的元素需要實作Comparable接口，否則将會出現異常。

// 存放資料
transient Object[] queue;

// 預設的初始容量
private static final int DEFAULT_INITIAL_CAPACITY = ;
 public PriorityQueue() {  this(DEFAULT_INITIAL_CAPACITY, null); } 
           

2.1 添加元素（add(E e)）

向優先級隊列中添加元素，實際上就是向堆中插入一個元素，當插入一個元素後，為了滿足堆的性質（父結點的值要麼都大于左右子結點，要麼都小于左右子結點），是以可能需要堆化。下面是Java中PriorityQueue的add(E e)方法實作，你可以對照着上篇文章中堆插入資料的過程來看。

public boolean add(E e) {
    // 直接調用offer(E e)
    return offer(e);
}

public boolean offer(E e) {  if (e == null)  throw new NullPointerException();  modCount++;  int i = size;  // 判斷是否需要擴容  if (i >= queue.length)  grow(i + ); // 擴容  size = i + ; // 将以存放的資料個數+1  if (i == ) // 第一個元素就不需要判斷是否要堆化了，直接加入即可  queue[] = e;  else  siftUp(i, e); // 從下往上堆化  return true; } 
           

可以看到，核心代碼在「siftUp()」 方法中，該方法從名字上就能推測出，是從下往上進行堆化。代碼實作如下：

private void siftUp(int k, E x) {
    if (comparator != null)
        siftUpUsingComparator(k, x);    // 如果指定了比較器，則采用指定的比較器來判斷元素的大小，進而進行堆化
    else
        siftUpComparable(k, x); // 沒有指定比較器，那添加到隊列中的元素必須實作了Comparable接口
} 
           

這裡我們以 「siftUpComparable()」 方法為例分析，其實這兩個方法的實作邏輯一樣，不同的是怎麼比較兩個元素的大小。

// 從下往上堆化
private void siftUpComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>) x;
    while (k > ) {
        int parent = (k - ) >>> ; // 數組索引除以2，實際上就是計算父結點的索引
 Object e = queue[parent];  if (key.compareTo((E) e) >= ) // 目前結點與父結點進行比較  break;  queue[k] = e;  k = parent;  }  queue[k] = key; } 
           

在從下往上堆化的過程中，先就算出父結點的位置，然後和父結點比較大小，根據比較的結果，判斷是否還需要繼續向上堆化。這段代碼和上一篇文章中堆化的代碼幾乎一樣，可以對照着來看。

2.2 取出元素（poll()）

實際上從優先級隊列中取出元素的過程，就是删除堆頂元素的過程。在删除完堆頂元素後，為了滿足堆的性質，是以需要進行堆化。比較簡單的做法就是，将數組中最後的一個元素搬到堆頂，然後再從上到下來進行堆化。poll()方法的源碼實作如下：

public E poll() {
    if (size == )
        return null;
    int s = --size;
    modCount++;
 // 取出堆頂元素  E result = (E) queue[];  // 取出數組的最後一個元素  E x = (E) queue[s];  queue[s] = null;  if (s != )  siftDown(, x); // 将數組的最後一個元素取出後，放到堆頂，然後從上往下堆化  return result; } 
           

可以看到，核心代碼實作在「siftDown()」 方法中，該方法的作用就是從上往下堆化。

// 從上往下堆化
private void siftDown(int k, E x) {
    if (comparator != null)
        siftDownUsingComparator(k, x);  // 有比較器
    else
 siftDownComparable(k, x); // 元素自己實作Compareable接口 } 
           

有比較器和無比較器的實作邏輯幾乎一緻，下面隻以「siftDownComparable()」 方法為例，看看從上往下的堆化過程。

private void siftDownComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>)x;
    // 葉子結點不需要堆化，是以需要計算出非葉子結點的位置
    int half = size >>> ;        // loop while a non-leaf
    while (k < half) {
 // 計算左子結點的位置  int child = (k << ) + ; // assume left child is least  Object c = queue[child];  // 右子結點的位置  int right = child + ;  if (right < size &&  ((Comparable<? super E>) c).compareTo((E) queue[right]) > )  c = queue[child = right];  if (key.compareTo((E) c) <= )  break;  queue[k] = c;  k = child;  }  queue[k] = key; } 
           

從上往下堆化的過程當中，「葉子節點是不需要進行堆化的」，是以代碼中，先計算出了處于數組最後面的非葉子結點的位置：「int half = size >>> 1」 (>>>的含義是無符号右移， 「>>> 1」 實際上就是除以2)。 接着分别将目前結點的值與左右兩個結點的值比較，判斷是否需要交換。這段代碼的邏輯和上篇文章中heapify()方法的邏輯是一緻的，可以對照着來看。堆化完，最終堆頂的元素就又變成了優先級最大或者最小的元素了。

3 總結

優先級隊列PriorityQueue的底層實作，實際上就是堆的實作，底層采用數組來存放資料，在插入資料時，采用的是從下往上進行堆化；取出元素時，實際上就是删除堆頂元素，這個過程采用的是從上往下進行堆化。