优先队列PriorityQueue源码解析

基本信息

实现了队列接口：Queue --> AbstractQueue --> PriorityQueue

public class PriorityQueue<E> extends AbstractQueue<E> implements java.io.Serializable {public abstract class AbstractQueue<E> extends AbstractCollection<E>implements Queue<E> {

底层 逻辑 数据结构: 堆
底层 物理 数据结构：数组

    // 默认数组长度11private static final int DEFAULT_INITIAL_CAPACITY = 11;// transient: JVM在对象序列化时忽略指定变量，从而避免数据泄露的安全问题transient Object[] queue; private int size = 0;// 定义的比较器，否则用元素的默认顺序private final Comparator<? super E> comparator;

元素不能为null，看下面initElementsFromCollection函数、及offer函数

关键函数

添加元素

public boolean add(E e) {// 直接调用offerreturn 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// 把e放在了末尾i位置，故要进行 上滤 操作siftUp(i, e);return true;}

弹出元素

public E poll() {if (size == 0)return null;int s = --size;modCount++;// 默认第0个元素就是要弹出的元素E result = (E) queue[0];E x = (E) queue[s];queue[s] = null;if (s != 0)siftDown(0, x);return result;}

peek函数

// 返回头部元素，并不会删除元素
public E peek() {return (size == 0) ? null : (E) queue[0];}

从集合初始化

public PriorityQueue(Collection<? extends E> c) {if (c instanceof SortedSet<?>) {SortedSet<? extends E> ss = (SortedSet<? extends E>) c;this.comparator = (Comparator<? super E>) ss.comparator();initElementsFromCollection(ss);}else if (c instanceof PriorityQueue<?>) {PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;this.comparator = (Comparator<? super E>) pq.comparator();initFromPriorityQueue(pq);}else {// 通常情况下，从集合初始化，则不能指定comparatorthis.comparator = null;initFromCollection(c);}}private void initFromCollection(Collection<? extends E> c) {// 从集合初始化数组、sizeinitElementsFromCollection(c);// 构建堆heapify();}
private void initElementsFromCollection(Collection<? extends E> c) {Object[] a = c.toArray();......int len = a.length;// 元素不能为nullif (len == 1 || this.comparator != null)for (int i = 0; i < len; i++)if (a[i] == null)throw new NullPointerException();this.queue = a;this.size = a.length;}private void heapify() {// 对数组 构建 堆for (int i = (size >>> 1) - 1; i >= 0; i--)siftDown(i, (E) queue[i]);}

上移、下降

下降

private void siftDown(int k, E x) {if (comparator != null)siftDownUsingComparator(k, x);elsesiftDownComparable(k, x);}private void siftDownUsingComparator(int k, E x) {int half = size >>> 1;// half还是叶子结点，若k=half，则k为叶子结点，无法向下了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];// x的值比左右子树 值 小，则当前位置就是目标位置if (comparator.compare(x, (E) c) <= 0)break;queue[k] = c;k = child;}// x从i位置下降到了k位置queue[k] = x;}

上移

private void siftUp(int k, E x) {if (comparator != null)siftUpUsingComparator(k, x);elsesiftUpComparable(k, x);}private void siftUpUsingComparator(int k, E x) {// 0位置无法上升了while (k > 0) {// 父节点位置：(k-1)/2int parent = (k - 1) >>> 1;Object e = queue[parent];// x比父节点小，则上移，否则，找到目标位置if (comparator.compare(x, (E) e) >= 0)break;queue[k] = e;k = parent;}// 目标位置放置xqueue[k] = x;}