PriorityQueue

1.1 特性

  • 基于优先堆的无界队列，默认自然排序或者实现Comparator
  • 不允许空值，不支持non-comparable，不可比较的对象
  • 队列头是基于自然排序的最小元素

  • 非线程安全的

    1.2 属性

    1. private static final int DEFAULT_INITIAL_CAPACITY = 11;
    3.   /**
    4.    * Priority queue represented as a balanced binary heap: the two
    5.    * children of queue[n] are queue[2*n+1] and queue[2*(n+1)].  The
    6.    * priority queue is ordered by comparator, or by the elements'
    7.    * natural ordering, if comparator is null: For each node n in the
    8.    * heap and each descendant d of n, n <= d.  The element with the
    9.    * lowest value is in queue[0], assuming the queue is nonempty.
    10.    */
    11.   transient Object[] queue; // non-private to simplify nested class access
    13.   /**
    14.    * The number of elements in the priority queue.
    15.    */
    16.   private int size = 0;
    18.   /**
    19.    * The comparator, or null if priority queue uses elements'
    20.    * natural ordering.
    21.    */
    22.   private final Comparator<? super E> comparator;
    24.   /**
    25.    * The number of times this priority queue has been
    26.    * <i>structurally modified</i>.  See AbstractList for gory details.
    27.    */
    28.   transient int modCount = 0; // non-private to simplify nested class access

    1.3 重要方法

    1.3.1 add&offer

    ```java //添加到队列末尾
    public boolean add(E e) {

    1.   return offer(e);

    }

//插入元素 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) queue[0] = e; else siftUp(i, e); return true; }

  1. private void siftUp(int k, E x) {
  2.     if (comparator != null)
  3.         siftUpUsingComparator(k, x);
  4.     else
  5.         siftUpComparable(k, x);
  6. }
  8. @SuppressWarnings("unchecked")
  9. private void siftUpComparable(int k, E x) {
  10.     Comparable<? super E> key = (Comparable<? super E>) x;
  11.     // 循环数组进行对比 挨个挪动
  12.     while (k > 0) {
  13.         int parent = (k - 1) >>> 1;
  14.         Object e = queue[parent];
  15.         if (key.compareTo((E) e) >= 0)
  16.             break;
  17.         queue[k] = e;
  18.         k = parent;
  19.     }
  20.     queue[k] = key;
  21. }
  23. @SuppressWarnings("unchecked")
  24. private void siftUpUsingComparator(int k, E x) {
  25.     while (k > 0) {
  26.         // 循环数组进行对比 挨个挪动
  27.         int parent = (k - 1) >>> 1;
  28.         Object e = queue[parent];
  29.         if (comparator.compare(x, (E) e) >= 0)
  30.             break;
  31.         queue[k] = e;
  32.         k = parent;
  33.     }
  34.     queue[k] = x;
  35. }
  1. <a name="xeCGM"></a>
  2. ### 1.3.2 peek
  3. ```java
  4.     public E peek() {
  5.         return (size == 0) ? null : (E) queue[0];
  6.     }

1.3.3 poll

  1. //出队对头元素，内部是调用 sifDown 挨个前移    
  2. public E poll() {
  3.         if (size == 0)
  4.             return null;
  5.         int s = --size;
  6.         modCount++;
  7.         E result = (E) queue[0];
  8.         E x = (E) queue[s];
  9.         queue[s] = null;
  10.         if (s != 0)
  11.             siftDown(0, x);
  12.         return result;
  13.     }

ConcurrentLinkedQueue

2.1 特性