PriorityQueue 源码分析

发表于 | 分类于 | 阅读次数：

[toc]

前言

PriorityQueue，即优先队列，队列中的元素依据某种规则进行排序，包括自然排序和定制排序。优先队列不允许插入 null，如果要使用自然排序，那么存储的对象必须实现 Comparable 接口。

本文将分析优先队列的构造、入队、出队等操作，其中又涉及到了扩容、上浮调整、下沉调整等。

以下代码基于 JDK 1.8

主要成员变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 默认初始容量
private static final int DEFAULT_INITIAL_CAPACITY = 11;

   /**
    * 优先队列基于二叉堆，所以用数组存储元素
 * queue[n] 的两个子节点分别为 queue[2*n + 1] 和 queue[2*n + 2]
    */
   transient Object[] queue; 

   /**
    * 优先队列中的元素个数
    */
   private int size = 0;

   /**
    * 用于定制排序，该值为 null 时表示使用自然排序（Comparable）
    */
   private final Comparator<? super E> comparator;

   /**
    * 修改次数
    */
   transient int modCount = 0;

构造方法

PriorityQueue 的构造方法有多个，主要分两类，一类需要传入集合，另一类不需要传入集合。

传入集合时如果原来的元素还没有排序，例如传入 List，则要重新排序，如果传入的是 TreeSet，就不需要重新排序了。

主要看另一类，另一类就比较简单，只是初始化了初始容量和 Comparator。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public PriorityQueue() {
    this(DEFAULT_INITIAL_CAPACITY, null);
}

public PriorityQueue(int initialCapacity) {
    this(initialCapacity, null);
}

public PriorityQueue(Comparator<? super E> comparator) {
    this(DEFAULT_INITIAL_CAPACITY, comparator);
}

public PriorityQueue(int initialCapacity,
                     Comparator<? super E> comparator) {
    if (initialCapacity < 1)
        throw new IllegalArgumentException();
    this.queue = new Object[initialCapacity];
    this.comparator = comparator;
}

入队

下面看一下入队，即添加元素的操作。入队主要有两个方法：add 和 offer。其中 add 方法调用的是 offer 方法：

1
2
3
public boolean add(E e) {
    return offer(e);
}

所以主要看 offer 方法：

offer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
  public boolean offer(E e) {
// 不能插入 null
      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;
  }

该方法还是比较容易看懂的，主要就是先判断是否要扩容，然后将元素插入到合适位置。

下面分别看下其中的 grow 和 siftUp 方法：

grow

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
  private void grow(int minCapacity) {
      int oldCapacity = queue.length;      
// 如果旧容量小于 64，新容量为旧容量的两倍加 2，即插入新元素后还有一半空间
// 否则新容量比旧容量增加百分之五十
      int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                       (oldCapacity + 2) :
                                       (oldCapacity >> 1));
      // 如果新容量大于 Integer.MAX_VALUE - 8 时，那么在最低容量不大于该值时，新容量为 Integer.MAX_VALUE - 8
// 这是因为一些 VM 在阵列中保留一些标题字，尝试分配更大的数组可能会导致OutOfMemoryError
// 如果最低容量大于该值，那么新容量为 Integer.MAX_VALUE
      if (newCapacity - MAX_ARRAY_SIZE > 0)
          newCapacity = hugeCapacity(minCapacity);

      queue = Arrays.copyOf(queue, newCapacity);
  }

该方法用于扩容，对于新容量，如果旧容量小于 64，新容量为旧容量的两倍加 2，即插入新元素后还有一半空间，否则新容量比旧容量增加百分之五十。

siftUp

1
2
3
4
5
6
private void siftUp(int k, E x) {
    if (comparator != null)
        siftUpUsingComparator(k, x);
    else
        siftUpComparable(k, x);
}

该方法的第一个参数为要填充的位置，第二个参数为插入的对象。根据不同排序使用不同方法，不过这两个方法大同小异，这里只分析自然排序的情况，即 siftUpComparable 方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
  private void siftUpComparable(int k, E x) {
// 如果 x 没有实现 Comparable 接口，将会抛出 ClassCastException 异常
      Comparable<? super E> key = (Comparable<? super E>) x;

      while (k > 0) {
	// 父节点的位置及元素
          int parent = (k - 1) >>> 1;		
          Object e = queue[parent];
	// 如果插入节点大于等于父节点，退出循环
          if (key.compareTo((E) e) >= 0)
              break;
	// 否则父节点下沉，插入节点上浮
          queue[k] = e;
          k = parent;
      }
// 插入节点回到正确位置
      queue[k] = key;
  }

可以看到，插入节点一开始插入到最后，然后进行上浮，回归到正确位置。另外，这是一个小顶堆，即最小的元素在堆顶（queue[0]）。

出队

看完入队操作，现在来看下出队操作。出队操作主要有两个方法：peek 和 poll。

其中 peek 方法获取但不删除队头元素。如果此队列为空，则返回 null。poll 方法获取并删除队头元素。如果此队列为空，则返回 null。

下面分别看下这两个方法：

peek

1
2
3
public E peek() {
    return (size == 0) ? null : (E) queue[0];
}

这个方法很简单，不多说了。下面看 poll 方法：

poll

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
  public E poll() {
      if (size == 0)
          return null;
      int s = --size;	// s = size - 1; size = size - 1;
      modCount++;
      E result = (E) queue[0];	// 保存队头元素

      E x = (E) queue[s];		// 保存队尾元素
      queue[s] = null;		// 将队尾元素置空，即删除队尾元素
// 如果删除的元素不是队头元素，那么将原先的队尾放到队头，并进行下沉调整
      if (s != 0)
          siftDown(0, x);

      return result;
  }

该方法也是返回队头元素，不过多了一步删除队头元素的操作。删除队头元素时，将原来的队尾元素放到队头，然后删除队尾元素，并对新的队头进行下沉调整。下沉调整用到了 siftDown 方法：

siftDown

1
2
3
4
5
6
private void siftDown(int k, E x) {
    if (comparator != null)
        siftDownUsingComparator(k, x);
    else
        siftDownComparable(k, x);
}

该方法和 siftUp 方法类似，第一个参数为插入位置，第二个参数为插入元素。然后从这个位置开始进行下沉操作。以自然排序为例，看 siftDownComparable 方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
  private void siftDownComparable(int k, E x) {
      Comparable<? super E> key = (Comparable<? super 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 &&
              ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
		// 如果右孩子比左孩子更小，将下沉节点更新为右孩子
              c = queue[child = right];
	
	// 如果插入节点小于等于子节点，不用继续下沉，退出循环
          if (key.compareTo((E) c) <= 0)
              break;
	// 子节点上浮
          queue[k] = c;
          k = child;
      }
// 插入节点回归到正确位置
      queue[k] = key;
  }

下沉的时候和上浮相反，和较小的子节点交换位置，直到下沉到正确位置。

小结

  1. 优先队列支持自然排序和定制排序，自然排序需要对象实现 Comparable 接口，定制排序需要传入 Comparator。
  2. 不能添加 null。
  3. 优先队列基于小顶堆，用数组存储元素，达到数组容量时进行扩容，在元素个数小于 64 时增加一倍，之后增加 0.5 倍。
  4. 添加元素到队尾以及删除队头元素时，都要进行调整。添加元素到队尾时，该元素进行上浮调整，上浮到合适的位置。删除队头元素时，将队尾元素移动到队头，并删除队尾元素，然后对新的队头元素进行下沉调整，下沉到合适的位置。
-------------　　　　本文到此结束　　感谢您的阅读　　　　-------------
0%