转载

JDK源码分析-PriorityQueue

概述

PriorityQueue 意为优先队列,表示队列中的元素是有优先级的,也就是说元素之间是可比较的。因此,插入队列的元素要实现 Comparable 接口或者 Comparator 接口。

PriorityQ ueue  的继承结构如下:

JDK源码分析-PriorityQueue

PriorityQueue 没有实现 BlockingQueue 接口,并非阻塞队列。 它在逻辑上使用「堆」(即完全二叉树)结构实现,物理上基于「动态数组」存储。如图所示:

JDK源码分析-PriorityQueue

有关堆的概念可参考前文「 数据结构与算法笔记(三) 」的相关描述。下面分析其代码实现。

代码分析

成员变量


 

// 数组的默认初始容量

private static final int DEFAULT_INITIAL_CAPACITY = 11;


// 内部数组,用于存储队列中的元素

transient Object[] queue; // non-private to simplify nested class access


// 队列中元素的个数

private int size = 0;


// 队列中元素的比较器

private final Comparator<? super E> comparator;


// 结构性修改次数

transient int modCount = 0; // non-private to simplify nested class access

构造器


 

// 构造器 1:无参构造器(默认初试容量为 11)

public PriorityQueue() {

this(DEFAULT_INITIAL_CAPACITY, null);

}


// 构造器 2:指定容量的构造器

public PriorityQueue(int initialCapacity) {

this(initialCapacity, null);

}


// 构造器 3:指定比较器的构造器

public PriorityQueue(Comparator<? super E> comparator) {

this(DEFAULT_INITIAL_CAPACITY, comparator);

}


// 构造器 4:指定初始容量和比较器的构造器

public PriorityQueue(int initialCapacity,

Comparator<? super E> comparator) {

// Note: This restriction of at least one is not actually needed,

// but continues for 1.5 compatibility

if (initialCapacity < 1)

throw new IllegalArgumentException();

// 初始化内部数组和比较器

this.queue = new Object[initialCapacity];

this.comparator = comparator;

}

这几个构造器的作用就是初始化内部数组和比较器。

此外,还有几个稍复杂点的构造器,代码如下:


 

// 构造器 5:用给定集合初始化 PriorityQueue 对象

public PriorityQueue(Collection<? extends E> c) {

// 如果集合是 SortedSet 类型

if (c instanceof SortedSet<?>) {

SortedSet<? extends E> ss = (SortedSet<? extends E>) c;

this.comparator = (Comparator<? super E>) ss.comparator();

initElementsFromCollection(ss);

}

// 如果集合是 PriorityQueue 类型

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);

}

}

initElementsFromCollection:


 

// 使用给定集合的元素初始化 PriorityQueue

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();

// 初始化 queue 数组和 size

this.queue = a;

this.size = a.length;

}

initFromPriorityQueue:


 

private void initFromPriorityQueue(PriorityQueue<? extends E> c) {

if (c.getClass() == PriorityQueue.class) {

// 若给定的是 PriorityQueue,则直接进行初始化

this.queue = c.toArray();

this.size = c.size();

} else {

initFromCollection(c);

}

}

initFromCollection:


 

private void initFromCollection(Collection<? extends E> c) {

// 将集合中的元素转为数组,并赋值给 queue(上面已分析)

initElementsFromCollection(c);

// 堆化

heapify();

}

heapify: 堆化,即将数组元素转为堆的存储结构


 

private void heapify() {

// 从数组的中间位置开始遍历即可

for (int i = (size >>> 1) - 1; i >= 0; i--)

siftDown(i, (E) queue[i]);

}

PS: 这里遍历时,从数组的中间位置遍历(根据堆的存储结构,如果某个节点的索引为 i,则其左右子节点的索引分别为 2 * i + 1,   2 * i + 2)。

siftDown: 向下筛选?暂未找到恰当的译法,但这不是重点,该方法的作用就是使数组满足堆结构(其思想与冒泡排序有些类似)。如下:


 

private void siftDown(int k, E x) {

// 根据 comparator 是否为空采用不同的方法

if (comparator != null)

siftDownUsingComparator(k, x);

else

siftDownComparable(k, x);

}

siftDownUsingComparator:


 

private void siftDownUsingComparator(int k, E x) {

// 数组的中间位置

int half = size >>> 1;

while (k < half) {

// 获取索引为 k 的节点的左子节点索引

int child = (k << 1) + 1;

// 获取 child 的值

Object c = queue[child];

// 获取索引为 k 的节点的右子节点索引

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;

}

queue[k] = x;

}

该方法的步骤大概:

1. 找出给定节点(父节点)的子节点中较小的一个,并于之比较大小;

2. 若父节点较大,则交换位置(父节点“下沉”)。

PS: 可参考上面的结构示意图, 其中数组表示队列中现有的元素,二叉树表示相应的堆结构, 角标表示数组中的索引(有兴趣可以在 IDE 断点调试验证)。

siftDownComparable 方法代码如下:


 

private void siftDownComparable(int k, E x) {

Comparable<? super E> key = (Comparable<? super E>)x;

int half = size >>> 1; // loop while a non-leaf

while (k < half) {

int child = (k << 1) + 1; // assume left child is least

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;

}

此方法与 siftDownUsingComparator 方法实现逻辑完全一样,不同的的地方仅在于该方法是针对 Comparable 接口,而后者针对 Comparator 接口,不再赘述。

此外 PriorityQueue 还有两个构造器,但都是通过上面的方法实现的,如下:


 

// 构造器 6:用给定的 PriorityQueue 初始化一个 PriorityQueue

public PriorityQueue(PriorityQueue<? extends E> c) {

this.comparator = (Comparator<? super E>) c.comparator();

initFromPriorityQueue(c);

}


// 构造器 7:用给定的 SortedSet 初始化 PriorityQueue

public PriorityQueue(SortedSet<? extends E> c) {

this.comparator = (Comparator<? super E>) c.comparator();

initElementsFromCollection(c);

}

也不再赘述。

入队操作 :add(E), offer(E)

两个入队操作方法如下:


 

// 实际是调用 offer 方法实现的

public boolean add(E e) {

return 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

// 向上筛选?

siftUp(i, e);

return true;

}

扩容操作:


 

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;


private void grow(int minCapacity) {

// 原先容量

int oldCapacity = queue.length;

// Double size if small; else grow by 50%

// 原容量较小时,扩大为原先的两倍;否则扩大为原先的 1.5 倍

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);

}


private static int hugeCapacity(int minCapacity) {

if (minCapacity < 0) // overflow

throw new OutOfMemoryError();

return (minCapacity > MAX_ARRAY_SIZE) ?

Integer.MAX_VALUE :

MAX_ARRAY_SIZE;

}

PS: 扩容操作与前文分析的 ArrayList 和 Vector 的扩容操作类似。

siftUp: 可与 siftDown 方法对比分析


 

private void siftUp(int k, E x) {

if (comparator != null)

siftUpUsingComparator(k, x);

else

siftUpComparable(k, x);

}

siftUpUsingComparator():


 

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;

}

该操作也稍微有点绕,还是以上图为基础继续操作,示意图如下:

JDK源码分析-PriorityQueue

其中分为左右两种情况:

1. 左边插入元素为 7,大于父节点 4,无需和父节点交换位置,直接插入即可;

2. 右边插入元素为 1,小于父节点 4,需要和父节点交换位置,并一直往上查找和交换,上图为调整后的数组及对应的树结构。

siftUpComparable: 


 

private void siftUpComparable(int k, E x) {

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;

}

该方法逻辑与 siftUpUsingComparator 一样,也是 Comparator 和 Comparable 接口的差别。

这里简单比较下  siftDown 和  siftUp 这两个方法:

1. siftDown 是把指定节点与其子节点中较小的一个比较,父节点较大时“下沉(down)”;

2. siftUp 是把指定节点与其父节点比较,若小于父节点,则“上浮(up)”。

出队操作 :poll()


 

public E poll() {

// 队列为空时,返回 null

if (size == 0)

return null;

int s = --size;

modCount++;

// 队列第一个元素

E result = (E) queue[0];

// 队列最后一个元素

E x = (E) queue[s];

// 把最后一个元素置空

queue[s] = null;

if (s != 0)

// 下沉

siftDown(0, x);

return result;

}

操作的示意图如下:

JDK源码分析-PriorityQueue

该操作的步骤大概如下:

1. 移除队列的最后一个元素,并将该元素置于首位;

2. 将新的“首位”元素与子节点中较小的一个比较,比较并交换位置(即执行“下沉(siftDown)”操作)。

删除操作 :remove(Object)


 

public boolean remove(Object o) {

int i = indexOf(o);

if (i == -1)

return false;

else {

removeAt(i);

return true;

}

}

indexOf(o):


 

// 遍历数组查找指定元素

private int indexOf(Object o) {

if (o != null) {

for (int i = 0; i < size; i++)

if (o.equals(queue[i]))

return i;

}

return -1;

}

removeAt(i):


 

private E removeAt(int i) {

// assert i >= 0 && i < size;

modCount++;

int s = --size;

// 移除末尾元素,直接置空

if (s == i) // removed last element

queue[i] = null;

else {

// 末尾元素

E moved = (E) queue[s];

queue[s] = null; // 删除末尾元素

// 操作与 poll 方法类似

siftDown(i, moved);

// 这里表示该节点未进行“下沉”调整,则执行“上浮“操作

if (queue[i] == moved) {

siftUp(i, moved);

if (queue[i] != moved)

return moved;

}

}

return null;

}

大概执行步骤:

1. 若移除末尾元素,直接删除;

2. 若非末尾元素,则将末尾元素删除,并用末尾元素替换待删除的元素;

3. 堆化操作:先执行“下沉(siftDown)”操作,若该元素未“下沉”,则再执行“上浮(siftUp)”操作,使得数组删除元素后仍满足堆结构。

示例代码

示例一:


 

private static void test1() {

// 不指定比较器(默认从小到大排序)

Queue<Integer> queue = new PriorityQueue<>();

for (int i = 0; i < 10; i++) {

queue.add(random.nextInt(100));

}

while (!queue.isEmpty()) {

System.out.print(queue.poll() + ". ");

}

}

/* 输出结果(仅供参考):

* 2, 13, 14, 36, 39, 40, 43, 55, 83, 88,

*/

示例二:指定比较器(Comparator)


 

private static void test2() {

// 指定比较器(从大到小排序)

Queue<Integer> queue = new PriorityQueue<>(11, (o1, o2) -> o2 - o1);

for (int i = 0; i < 10; i++) {

queue.add(random.nextInt(100));

}

while (!queue.isEmpty()) {

System.out.print(queue.poll() + ", ");

}

}

/* 输出结果(仅供参考):

* 76, 74, 71, 69, 52, 49, 41, 41, 35, 1,

*/

示例三:求 Top N


 

public class FixedPriorityQueue {

private PriorityQueue<Integer> queue;

private int maxSize;


public FixedPriorityQueue(int maxSize) {

this.maxSize = maxSize;

// 初始化优先队列及比较器

// 这里是从大到小(可调整)

this.queue = new PriorityQueue<>(maxSize, (o2, o1) -> o2.compareTo(o1));

}


public void add(Integer i) {

// 队列未满时,直接插入

if (queue.size() < maxSize) {

queue.add(i);

} else {

// 队列已满,将待插入元素与最小值比较

Integer peek = queue.peek();

if (i.compareTo(peek) > 0) {

// 大于最小值,将最小值移除,该元素插入

queue.poll();

queue.add(i);

}

}

}

public static void main(String[] args) {

FixedPriorityQueue fixedQueue = new FixedPriorityQueue(10);

for (int i = 1; i <= 100; i++) {

fixedQueue.add(i);

}

Iterable<Integer> iterable = () -> fixedQueue.queue.iterator();

System.out.println("队列中的元素:");

for (Integer integer : iterable) {

System.out.print(integer + ", ");

}

System.out.println();

System.out.println("最大的 10 个:");

while (!fixedQueue.queue.isEmpty()) {

System.out.print(fixedQueue.queue.poll() + ", ");

}

}


}

/* 输出结果:

* 队列中的元素:

* 91, 92, 94, 93, 96, 95, 99, 97, 98, 100,

* 最大的 10 个:

* 91, 92, 93, 94, 95, 96, 97, 98, 99, 100,

*/

小结

1. PriorityQueue 为优先队列,实现了 Queue 接口,但并非阻塞对列;

2. 内部的元素是可比较的(Comparable 或 Comparator),元素不能为空;

3. 逻辑上使用「堆」(即完全二叉树)结构实现,物理上基于「动态数组」存储;

4. PriorityQueue 可用作求解 Top N 问题。

参考链接:

https://blog.csdn.net/qq_35326718/article/details/72866180

https://my.oschina.net/leejun2005/blog/135085

Stay hungry, stay foolish.

JDK源码分析-PriorityQueue

原文  http://mp.weixin.qq.com/s?__biz=MzU4NzYyMDE4MQ==&mid=2247483966&idx=1&sn=02549063535d694338fc0a37c73b3f3c
正文到此结束
Loading...