认识

PriorityQueue 一个基于优先级的无界优先级队列。优先级队列的元素按照其自然顺序进行排序，或者根据构造队列时提供的 Comparator 进行排序，具体取决于所使用的构造方法。该队列不允许使用 null 元素也不允许插入不可比较的对象(没有实现Comparable接口的对象)。
PriorityQueue 队列的头是：指排序规则最小那个元素。如果多个元素都是最小值则随机选一个。
PriorityQueue 是一个无界队列，但是初始的容量(实际是一个Object[])，随着不断向优先级队列添加元素，其容量会自动扩容，无需指定容量增加策略的细节。

逻辑上使用堆结构（完全二叉树）实现，物理上使用动态数组实现，并非像TreeMap一样完全有序，但是如果按照指定方式出队，结果可以是有序的

类图关系

走进源码

数据结构

//队列transient Object[] queue;//队列长度private int size = 0;

3.1构造函数

• 空参构造函数

/***创建一个具有默认初始容量（11）的队列*该容量根据其元素进行排序*/public PriorityQueue() {this(DEFAULT_INITIAL_CAPACITY, null);}

• 指定初始容量，比较器

/*** 构造一个指定初始容量，构造起的队列*/public PriorityQueue(int initialCapacity,Comparator<? super E> comparator) {if (initialCapacity < 1)throw new IllegalArgumentException();this.queue = new Object[initialCapacity];this.comparator = comparator;}

• 指定初始容量，没有比较器，默认按照元素自然顺序排序

/***创建一个具指定容的队列*该容量根据其元素进行排序*/public PriorityQueue(int initialCapacity) {this(initialCapacity, null);}

• 默认初始容量，指定比较器

/*** 创建一个具有默认初始容量和的队列，其元素根据指定的比较器进行排序*/public PriorityQueue(Comparator<? super E> comparator) {this(DEFAULT_INITIAL_CAPACITY, comparator);}

• 根据集合c或者队列c，来构造队列，并带有指定元素

/***创建一个包含指定集合中元素的队列*如果集合是SortedSet，或者是PriorityQueue，则根据根据相同的顺序进行排序*否则根据元素的自然顺序排序*/@SuppressWarnings(\"unchecked\")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 {this.comparator = null;initFromCollection(c);}}

• 基于一个队列c，来构造新的队列，并带有指定元素

/*** 创建一个包含指定优先级队列中元素的队列，该优先级队列将根据与给定优先级队列相同的顺序进行排序*/@SuppressWarnings(\"unchecked\")public PriorityQueue(PriorityQueue<? extends E> c) {this.comparator = (Comparator<? super E>) c.comparator();initFromPriorityQueue(c);}

• 基于一个集合c，来构造新的队列，并带有指定的元素

/***创建一个队列，其中包含指定的排序集中的元素。*该优队列将根据与给定排序集相同的顺序进行排序*/@SuppressWarnings(\"unchecked\")public PriorityQueue(SortedSet<? extends E> c) {this.comparator = (Comparator<? super E>) c.comparator();initElementsFromCollection(c);}

initFromPriorityQueue（），initElementsFromCollection()方法，具体详细

//基于队列c,初始化队列的数据，队列大小private void initFromPriorityQueue(PriorityQueue<? extends E> c) {if (c.getClass() == PriorityQueue.class) {this.queue = c.toArray();this.size = c.size();} else {initFromCollection(c);}}//基于集合c，初始化新队列private void initElementsFromCollection(Collection<? extends E> c) {Object[] a = c.toArray();// If c.toArray incorrectly doesn\'t return Object[], copy it.if (a.getClass() != Object[].class)a = Arrays.copyOf(a, a.length, Object[].class);int len = a.length;if (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;}//基于集合c，初始化队列private void initFromCollection(Collection<? extends E> c) {initElementsFromCollection(c);heapify();}

3.2添加元素

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

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;elsesiftUp(i, e);return true;}

grow（）
扩容机制，如果原始容量<64,则按照容量翻倍来扩容
原始容量>64,那么 新容量=oldCapacity +oldCapacity /2

private void grow(int minCapacity) {int oldCapacity = queue.length;// Double size if small; else grow by 50%int newCapacity = oldCapacity + ((oldCapacity < 64) ?(oldCapacity + 2) :(oldCapacity >> 1));// overflow-conscious codeif (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);queue = Arrays.copyOf(queue, newCapacity);}

在位置k插入项x，通过将树上的x提升直到它大于或等于其父级或成为根，从而保持堆不变。 简化并加快强制和比较。 可比较和比较器版本分为不同的方法，这些方法在其他方面相同。 （类似于siftDown

private void siftUp(int k, E x) {if (comparator != null)siftUpUsingComparator(k, x);elsesiftUpComparable(k, x);}

private void siftUpUsingComparator(int k, E x) {while (k > 0) {//表示最后一个非叶子节点(父节点)的位置int parent = (k - 1) >>> 1;Object e = queue[parent];if (comparator.compare(x, (E) e) >= 0)break;queue[k] = e;k = parent;}queue[k] = x;}

compare()

//最大堆int compare(Integer x, Integer e){return x > e ? -1 : 1;}//最小堆int compare(Integer x, Integer e){return x < e ? -1 : 1;}

无论是添加元素，还是删除元素，实现的逻辑都是按照大根堆或者小根堆来实现

• 删除元素

public boolean remove(Object o) {int i = indexOf(o);if (i == -1)return false;else {removeAt(i);return true;}}

removeAt()删除指定位置的元素

private E removeAt(int i) {// assert i >= 0 && i < size;modCount++;int s = --size;if (s == i) // 删除队列末端元素queue[i] = null;else {E moved = (E) queue[s];queue[s] = null;siftDown(i, moved);if (queue[i] == moved) {siftUp(i, moved);if (queue[i] != moved)return moved;}}return null;}

• 删除指定元素对象

boolean removeEq(Object o) {for (int i = 0; i < size; i++) {if (o == queue[i]) {removeAt(i);return true;}}return false;}

3.3 查找

• 返回队列的第一个元素

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

-查找指定元素的下标位置

private int indexOf(Object o) {if (o != null) {for (int i = 0; i < size; i++)if (o.equals(queue[i]))return i;}return -1;}