詳解優先隊列在JDK中的實作方式

這篇文章主要為大家詳細介紹了JDK源碼之PriorityQueue，具有一定的參考價值，有興趣的小伙伴們可以參考一下

##一.優先隊列的應用

優先隊列在程式開發中屢見不鮮，例如作業系統在進行進程調度時一種可行的演算法是使用優先隊列，當一個新的進程被fork()出來後，首先將它放到隊列的最後，而作業系統內部的Scheduler負責不斷地從這個優先隊列中取出優先權較高的進程執行；爬蟲系統在執行時往往也需要從一個優先權隊列中

循環取出高優先級任務並進行抓取。可以想見，如果類似這樣的任務不適用優先權進行劃分的話，系統必會出現故障，例如操作系統中低優先權進程持續佔用資源而高優先權進程始終在佇列中等待。此外，優先隊列在貪婪演算法中也有一些應用。

二.優先佇列的實作原理

優先佇列的實作方式是使用二元堆的結構，需要滿足以下兩個性質(Heap property)，這裡以小頂堆為例講解：

　　1.任何結點的值都小於或等於其子節點的值。 　　2.所有結點從上到下，由左到右填入，即一棵完全二元樹。

基於這兩個規律，二元堆在實作中往往會使用一個

陣列，下面我們研究一下JDK中二元堆(優先佇列)的實作。

三.優先權佇列在JDK中的實作方式

研究原始碼最好的方式是debug，看每一步

變數的變化，我們可以簡單寫一個Demo，debug進源碼一探究竟：

#這裡我們簡單地創建一個優先隊列，向其中添加三個元素，我們可以在代碼第一行打一個斷點，如果您使用

Eclipse#編輯器的話，接下來可以按F5進入原始碼：

程式碼運行到這裡，PriorityQueue呼叫自己的一個

重載建構器，第一個參數是數組預設大小，第二個是元素比較的Comparator,我們這裡的Demo比較簡單，您在使用優先佇列時可以選擇實作自己的Comparator。

 public PriorityQueue(int initialCapacity,
             Comparator<? super E> comparator) {
    // Note: This restriction of at least one is not actually needed,
    // but continues for 1.5 compatibility
    if (initialCapacity < 1)
      throw new IllegalArgumentException();
    this.queue = new Object[initialCapacity];
    this.comparator = comparator;
  }

接下來我們研究一下加入元素時的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) 
      //第一次添加元素，直接放到第0个位置即可
      queue[0] = e;
    else
      //需要将元素放到最后，再做上滤操作
      siftUp(i, e);
    return true;
  }

我們逐行來解釋一下，首先offer方法判斷參數是否為空，不為空則對變數modCount自增，modCount記錄了佇列被修改的次數，接下來，判斷數組是否會越界，如果越界則透過grow進行擴容，接下來添加元素，如果當前元素為0個則直接將元素放到數組第一個位置，否則要做一個siftUp的操作。

 private void grow(int minCapacity) {
    int oldCapacity = queue.length;
    // Double size if small; else grow by 50%
    int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                     (oldCapacity + 2) :
                     (oldCapacity >> 1));
    // overflow-conscious code
    if (newCapacity - MAX_ARRAY_SIZE > 0)
      newCapacity = hugeCapacity(minCapacity);
    //元素拷贝
    queue = Arrays.copyOf(queue, newCapacity);

上面的程式碼對佇列擴容，原始碼中

註解也很清晰，首先判斷目前的陣列大小是否足夠小(<64)，如果夠小則將大小擴充為2倍，否則原大小加上50%。要注意的是，這裡最後做了一個大小是否溢出的判斷。

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

如果需要擴容的大小已經<0了，顯然已經溢出了，在這裡拋出了OutOfMemory的例外。

private void siftUpUsingComparator(int k, E x) {
    while (k > 0) {
      //计算父亲节点的下标
      int parent = (k - 1) >>> 1;
      Object e = queue[parent];
      //与父节点进行比较
      if (comparator.compare(x, (E) e) >= 0)
        break;
      queue[k] = e;
      k = parent;
    }
    queue[k] = x;
  }

為了確保優先隊列的性質1，在插入每個元素時都需要與該節點父親進行比較，找到其正確位置，有些數據結構書中，這個操作被稱為上濾(percolate up)。

入隊操作已經說完了，接下來是出隊操作，即poll()操作：

public E poll() {
    if (size == 0)
      return null;
    int s = --size;
    //自增变量，代表队列修改次数
    modCount++;
    E result = (E) queue[0];
    E x = (E) queue[s];
    queue[s] = null;
    if (s != 0)
      siftDown(0, x);
    return result;
  }

這個方法首先將數組第一個元素作為結果，(因為如果是小頂堆的話堆頂總是最小元素)，並將隊列的最後一個元素放到第一個位置，最後用siftDown做一些調整，保證隊列的性質，這個操作被稱為下濾(percolate down)。

 private void siftDownUsingComparator(int k, E x) {
 

    int half = size >>> 1;
    //这里k必须有孩子，故叶节点需要比较
    while (k < half) {
      //以下几行代码到较小的那个儿子,用变量c表示
      int child = (k << 1) + 1;
      //这里假设左儿子比较小
      Object c = queue[child];
      int right = child + 1;
      //左右儿子比较，如果右儿子小则将c赋值为右儿子
      if (right < size &&
        comparator.compare((E) c, (E) queue[right]) > 0)
        c = queue[child = right];
      //如果x比小儿子还小，说明k就是正确位置
      if (comparator.compare(x, (E) c) <= 0)
        break;
      queue[k] = c;
      k = child;
    }
    queue[k] = x;
  }

如上圖，下濾過程中k不斷與其兒子進行比較，如果滿足優先隊列的順序性，則break出循環。

【相關推薦】

1.

Java免費影片教學

#2.

全面解析Java註解

#3.

FastJson教學手冊

以上是詳解優先隊列在JDK中的實作方式的詳細內容。更多資訊請關注PHP中文網其他相關文章！