Java PriorityQueue 使用

本章主要介紹 PriorityQueue

PriorityQueue 是一個有排序功能的隊列，內部實際上是一棵堆排序的二叉樹數據結構

代碼示例：

package com.jacky.test;
import java.util.PriorityQueue;
public class PriorityQueueTest {
  public static void main(String[] args) {
    PriorityQueue<String> q = new PriorityQueue<>();
    q.add("c");
    q.add("e");
    q.add("a");
    q.add("d");
    q.add("z");
    int size = q.size();
    System.out.println(q + " | " + size);
    for (int i = 0; i < size; i++) {
      System.out.println(q.poll());
    }
  }
}

代碼解讀：將元素亂序加入隊列中，打印隊列元素是按照加入的順序，當使用 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;
}

private void siftDownUsingComparator(int k, E x) {
    int half = size >>> 1;
    while (k < half) {
        int child = (k << 1) + 1;
        Object c = queue[child];
        int right = child + 1;
        if (right < size &&
            comparator.compare((E) c, (E) queue[right]) > 0)
            c = queue[child = right];
        if (comparator.compare(x, (E) c) <= 0)
            break;
        queue[k] = c;
        k = child;
    }
    queue[k] = x;
}

閱讀源碼發現，讀取元素時，調用 siftDown 進行篩選，會將元素進行排序比較，所以取得的結果就是排好序的。

引申：前面介紹 DelayQueue，實際上內部使用的就是 PriorityQueue，具體見源碼

public class DelayQueue<E extends Delayed> extends AbstractQueue<E>
    implements BlockingQueue<E> {
    private final transient ReentrantLock lock = new ReentrantLock();
    private final PriorityQueue<E> q = new PriorityQueue<E>();
    ......

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/G3CXhNLozp5X9H1Zn8izxw