https://blog.csdn.net/u010675669/article/details/86503464

源码@since 1.5

类继承

  1. class PriorityQueue<E> extends AbstractQueue<E> implements java.io.Serializable

常量值

  1. private static final int DEFAULT_INITIAL_CAPACITY = 11;

变量(未搞明白)

  1. // 优先级队列表示为一个平衡的二进制堆:queue[n]的两个子队列是queue[2n+1]和queue[2(n+1)]。对于堆中的每个节点n和n的每个后代节点d, n <= d。如果队列非空，值最小的元素在队列[0]中。
  2. transient Object[] queue; 
  4. private int size = 0;
  6. // 这个优先队列在结构上被修改的次数。详情请参阅AbstractList。
  7. transient int modCount = 0;
  9. private final Comparator<? super E> comparator;

构造函数

  1. public PriorityQueue() {
  2.         this(DEFAULT_INITIAL_CAPACITY, null);
  3.     }
  5. public PriorityQueue(int initialCapacity) {
  6.         this(initialCapacity, null);
  7.     }
  9. // @since 1.8
  10. public PriorityQueue(Comparator<? super E> comparator) {
  11.         this(DEFAULT_INITIAL_CAPACITY, comparator);
  12.     }
  15. // 实现逻辑 
  16. public PriorityQueue(int initialCapacity,
  17.                          Comparator<? super E> comparator) {
  18.         // Note: This restriction of at least one is not actually needed,
  19.         // but continues for 1.5 compatibility
  20.         if (initialCapacity < 1)
  21.             throw new IllegalArgumentException();
  22.         this.queue = new Object[initialCapacity];
  23.         this.comparator = comparator;
  24.     }
  26. // 使用集合
  27. public PriorityQueue(Collection<? extends E> c) {
  28.         if (c instanceof SortedSet<?>) {
  29.             SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
  30.             this.comparator = (Comparator<? super E>) ss.comparator();
  31.             initElementsFromCollection(ss);
  32.         }
  33.         else if (c instanceof PriorityQueue<?>) {
  34.             PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
  35.             this.comparator = (Comparator<? super E>) pq.comparator();
  36.             initFromPriorityQueue(pq);
  37.         }
  38.         else {
  39.             this.comparator = null;
  40.             initFromCollection(c);
  41.         }
  42.     }
  44. // 使用PriorityQueue
  45. public PriorityQueue(PriorityQueue<? extends E> c) {
  46.         this.comparator = (Comparator<? super E>) c.comparator();
  47.         initFromPriorityQueue(c);
  48.     }
  49. private void initFromPriorityQueue(PriorityQueue<? extends E> c) {
  50.     if (c.getClass() == PriorityQueue.class) {
  51.         this.queue = c.toArray();
  52.         this.size = c.size();
  53.     } else {
  54.         initFromCollection(c);
  55.     }
  56. }
  57. private void initFromCollection(Collection<? extends E> c) {
  58.     initElementsFromCollection(c);
  59.     heapify();
  60. }
  61. private void heapify() {
  62.     for (int i = (size >>> 1) - 1; i >= 0; i--)
  63.         siftDown(i, (E) queue[i]);
  64. }
  65. private void siftDown(int k, E x) {
  66.     if (comparator != null)
  67.         siftDownUsingComparator(k, x);
  68.     else
  69.         siftDownComparable(k, x);
  70. }
  71. private void siftDownComparable(int k, E x) {
  72.     Comparable<? super E> key = (Comparable<? super E>)x;
  73.     int half = size >>> 1;        // loop while a non-leaf
  74.     while (k < half) {
  75.         int child = (k << 1) + 1; // assume left child is least
  76.         Object c = queue[child];
  77.         int right = child + 1;
  78.         if (right < size &&
  79.             ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
  80.             c = queue[child = right];
  81.         if (key.compareTo((E) c) <= 0)
  82.             break;
  83.         queue[k] = c;
  84.         k = child;
  85.     }
  86.     queue[k] = key;
  87. }
  88. private void siftDownUsingComparator(int k, E x) {
  89.     int half = size >>> 1;
  90.     while (k < half) {
  91.         int child = (k << 1) + 1;
  92.         Object c = queue[child];
  93.         int right = child + 1;
  94.         if (right < size &&
  95.             comparator.compare((E) c, (E) queue[right]) > 0)
  96.             c = queue[child = right];
  97.         if (comparator.compare(x, (E) c) <= 0)
  98.             break;
  99.         queue[k] = c;
  100.         k = child;
  101.     }
  102.     queue[k] = x;
  103. }
  104. // 使用SortedSet
  105. public PriorityQueue(SortedSet<? extends E> c) {
  106.         this.comparator = (Comparator<? super E>) c.comparator();
  107.         initElementsFromCollection(c);
  108.     }
  109. private void initElementsFromCollection(Collection<? extends E> c) {
  110.     Object[] a = c.toArray();
  111.     // If c.toArray incorrectly doesn't return Object[], copy it.
  112.     if (a.getClass() != Object[].class)
  113.         a = Arrays.copyOf(a, a.length, Object[].class);
  114.     int len = a.length;
  115.     if (len == 1 || this.comparator != null)
  116.         for (int i = 0; i < len; i++)
  117.             if (a[i] == null)
  118.                 throw new NullPointerException();
  119.     this.queue = a;
  120.     this.size = a.length;
  121. }

常用方法