PriorityQueue
逻辑上使用堆结构（完全二叉树）实现，物理上使用动态数组实现，并非像TreeMap一样完全有序，但是如果按照指定方式出队，结果可以是有序的。
先看题目
在未排序的数组中找到第 k个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
输入：3,2,3,1,2,4,5,5,6，k =4。输出就是4，因此重复的并不考虑。
一般解法
public static int findKthLargest(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length - k];
}
优先队列解法
public static int findKthLargest(int[] nums, int k) {
Queue<Integer> queue = new PriorityQueue<>();
for (int num : nums) {
queue.add(num);
if (queue.size() > k) {
//返回队首元素，队首元素出队列
queue.poll();
}
}
//返回队首元素
return queue.peek();
}
适用场景
一般用于队列中某些元素需要优先处理的情况
成员变量
//默认容量 数据结构实现基于数组 支持扩容
private static final int DEFAULT_INITIAL_CAPACITY = 11;
/**
* Priority queue represented as a balanced binary heap: the two
* children of queue[n] are queue[2*n+1] and queue[2*(n+1)]. The
* priority queue is ordered by comparator, or by the elements'
* natural ordering, if comparator is null: For each node n in the
* heap and each descendant d of n, n <= d. The element with the
* lowest value is in queue[0], assuming the queue is nonempty.
*/
transient Object[] queue; // non-private to simplify nested class access
/**
* The number of elements in the priority queue.
* 队列大小
*/
private int size = 0;
/**
* The comparator, or null if priority queue uses elements'
* natural ordering.
* 比较接口
*/
private final Comparator<? super E> comparator;
/**
* The number of times this priority queue has been
* <i>structurally modified</i>. See AbstractList for gory details.
* 修改次数
*/
transient int modCount = 0; // non-private to simplify nested class access
构造方法
//指定容量
public PriorityQueue(int initialCapacity) {
this(initialCapacity, null);
}
//指定比较接口(一般用于比较对象优先级时使用 默认按照自然升序)
public PriorityQueue(Comparator<? super E> comparator) {
this(DEFAULT_INITIAL_CAPACITY, comparator);
}
主要方法
添加 add(E e)
public boolean add(E e) {
return offer(e);
}
public boolean offer(E e) {
// 元素不能为空
if (e == null)
throw new NullPointerException();
//修改次数加1
modCount++;
int i = size;
// 容量不够 需要扩容
if (i >= queue.length)
grow(i + 1);
// 容量+1
size = i + 1;
//如果不存在元素 添加的首部
if (i == 0)
queue[0] = e;
else
// 添加元素
siftUp(i, e);
return true;
}
扩容 grow(int minCapacity)
/**
* Increases the capacity of the array.
*
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
int oldCapacity = queue.length;
// Double size if small; else grow by 50% 小的话加倍；否则增长 50%
int newCapacity = oldCapacity + ((oldCapacity < 64) ?
(oldCapacity + 2) :
(oldCapacity >> 1));
// overflow-conscious code 大容量
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
queue = Arrays.copyOf(queue, newCapacity);
}
添加(上移) siftUp(int k, E x)
/**
* Inserts item x at position k, maintaining heap invariant by
* promoting x up the tree until it is greater than or equal to
* its parent, or is the root.
*
* To simplify and speed up coercions and comparisons. the
* Comparable and Comparator versions are separated into different
* methods that are otherwise identical. (Similarly for siftDown.)
*
* @param k the position to fill 添加的位置
* @param x the item to insert 插入的元素
*/
private void siftUp(int k, E x) {
// 定义比较器
if (comparator != null)
siftUpUsingComparator(k, x);
else
// 没有定义了比较器
siftUpComparable(k, x);
}
未定义了比较器的上移 siftUpComparable(int k, E x)
/**
* 上移，x表示新插入元素，k表示新插入元素在数组的位置
*/
private void siftUpComparable(int k, E x) {
// 比较器comparator为空，需要插入的元素实现Comparable接口，用于比较大小
Comparable<? super E> key = (Comparable<? super E>) x
//k>0表示判断k不是根的情况下，也就是元素x有父节点
while (k > 0) {
// 计算元素x的父节点位置[(n-1)/2]
int parent = (k - 1) >>> 1;
// 取出x的父亲e
Object e = queue[parent];
// 如果新增的元素k比其父亲e大，则不需要"上移"，跳出循环结束
if (key.compareTo((E) e) >= 0)
break;
// x比父亲小，则需要进行"上移"
// 交换元素x和父亲e的位置
queue[k] = e;
// 将新插入元素的位置k指向父亲的位置，进行下一层循环
k = parent;
}
// 找到新增元素x的合适位置k之后进行赋值
queue[k] = key;
}
定义比较器的上移 private void siftUpUsingComparator(int k, E x)
// jdk 1.8 同上面的操作
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;
}
获取方法
获取首元素
public E peek() {
return (size == 0) ? null : (E) queue[0];
}
获取首元素 首元素弹出
public E poll() {
if (size == 0)
return null;
// 容量减少1
int s = --size;
// 修改次数+1
modCount++;
//去除第一个元素
E result = (E) queue[0];
E x = (E) queue[s];
queue[s] = null;
if (s != 0)
siftDown(0, x);
return result;
}
private void siftDownComparable(int k, E x) {
// 比较器comparator为空，需要插入的元素实现Comparable接口，用于比较大小
Comparable<? super E> key = (Comparable<? super E>)x;
// 通过size/2找到一个没有叶子节点的元素
int half = size >>> 1; // loop while a non-leaf
// 比较位置k和half，如果k小于half，则k位置的元素就不是叶子节点
while (k < half) {
// 找到根元素的左孩子的位置[2n+1]
int child = (k << 1) + 1; // assume left child is least
// 左孩子的元素
Object c = queue[child];
// 找到根元素的右孩子的位置[2(n+1)]
int right = child + 1;
// 如果左孩子大于右孩子，则将c复制为右孩子的值，这里也就是找出左右孩子哪个最小
if (right < size &&
((Comparable<? super E>) c).compareTo((E) queue [right]) > 0)
c = queue[child = right];
// 如果队尾元素比根元素孩子都要小，则不需"下移"，结束
if (key.compareTo((E) c) <= 0)
break;
// 队尾元素比根元素孩子都大，则需要"下移"
// 交换跟元素和孩子c的位置
queue[k] = c;
// 将根元素位置k指向最小孩子的位置，进入下层循环
k = child;
}
// 找到队尾元素x的合适位置k之后进行赋值
![GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)