【数据结构】Java 常用集合类 PriorityQueue

用户头像
Alex🐒
关注
发布于: 2020 年 07 月 22 日

PriorityQueue 整体设计

PriorityQueue 继承自抽象父类 AbstractQueue 的优先级队列,使用小顶堆实现每次取出的元素都是队列中权值最小的。元素大小的判断可以通过传入的比较器计算,否则采用自然排序。不允许放入 null。



按照堆的特点可以把堆分为大顶堆和*小顶堆*

大顶堆:每个结点的值都大于或*等于*其左右孩子结点的值

小顶堆:每个结点的值都小于或*等于*其左右孩子结点的值



public class PriorityQueue<E> extends AbstractQueue<E>
implements java.io.Serializable {
}

PriorityQueue 属性和构造函数

主要属性

// 默认初始容量
private static final int DEFAULT_INITIAL_CAPACITY = 11;
// 表示为平衡二叉堆的优先级队列:queue[n]的两个子节点列是queue[2*n+1]和queue[2*(n+1)]
transient Object[] queue;
// 队列元素数量
private int size = 0;
// 比较器,用于定义比较规则
private final Comparator<? super E> comparator;



构造函数

// 默认构造器
public PriorityQueue() {
this(DEFAULT_INITIAL_CAPACITY, null);
}
// 指定初始容量
public PriorityQueue(int initialCapacity) {
this(initialCapacity, null);
}
// 对初始容量的要求 >= 1
public PriorityQueue(int initialCapacity,
Comparator<? super E> comparator) {
if (initialCapacity < 1)
throw new IllegalArgumentException();
this.queue = new Object[initialCapacity];
this.comparator = comparator;
}
// 对 SortedSet 和 PriorityQueue 特殊处理
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);
}
}



使用 SortedSet 初始化,已经是排序数组,直接赋值

private void initElementsFromCollection(Collection<? extends E> c) {
Object[] a = c.toArray();
if (a.getClass() != Object[].class)
a = Arrays.copyOf(a, a.length, Object[].class);
int len = a.length;
// 不支持有 null 元素
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;
}



使用 PriorityQueue 初始化,直接赋值

private void initFromPriorityQueue(PriorityQueue<? extends E> c) {
if (c.getClass() == PriorityQueue.class) {
this.queue = c.toArray();
this.size = c.size();
} else {
initFromCollection(c);
}
}



使用其他集合类初始化,调用 heapify() 调整顺序

private void initFromCollection(Collection<? extends E> c) {
initElementsFromCollection(c);
heapify();
}

添加元素

可以调用 add()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;
}

向上调整元素

不断地和 parent(queue[(k-1)/2])比较,如果小于 parent 进行互换

// k 当前位置,x 当前元素,向上调整
private void siftUp(int k, E x) {
// 选择比较器
if (comparator != null)
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x);
}
// 默认比较器
private void siftUpComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>) x;
while (k > 0) {
// 找到 parent,如果小于 parent,进行换位
int parent = (k - 1) >>> 1;
Object e = queue[parent];
if (key.compareTo((E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = key;
}
// 使用指定比较器
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;
}

扩容 grow

如果 queue 数组已经占满,进行扩容,扩容后大小计算以 64 为分界线,并且如果 newCapacity 增加到 MAXARRAYSIZE,调用 hugeCapacity() 计算的到。扩容是通过数组拷贝的方式。

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%
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) {
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}

取出元素

peek() 方法返回堆顶元素,poll() 方法返回并移除堆顶元素

public E peek() {
return (size == 0) ? null : (E) queue[0];
}
public E poll() {
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;
}

向下调整元素

private void siftDown(int k, E x) {
if (comparator != null)
siftDownUsingComparator(k, x);
else
siftDownComparable(k, x);
}
// child默认为小的那个下标,记录小的对象为c;,就结束循环,调整完成,否则将c赋值为queue[k],k = child,继续向下调整。
private void siftDownUsingComparator(int k, E x) {
// 最后一层非叶子节点层
int half = size >>> 1;
while (k < half) {
// k的左子节点child,右子节点right
int child = (k << 1) + 1;
Object c = queue[child];
int right = child + 1;
// 如果右子节点存在,找到比较小的子节点,作为c取出,下标为child
if (right < size &&
comparator.compare((E) c, (E) queue[right]) > 0)
c = queue[child = right];
// 如果x大于c,进行交换,并进入下一层循环
if (comparator.compare(x, (E) c) <= 0)
break;
queue[k] = c;
k = child;
}
queue[k] = x;
}
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;
}

删除元素

默认删除堆顶元素,如果删除指定元素先找到元素位置,然后移除

public E remove() {
E x = poll();
if (x != null)
return x;
else
throw new NoSuchElementException();
}
// 先找到元素位置
public boolean remove(Object o) {
int i = indexOf(o);
if (i == -1)
return false;
else {
removeAt(i);
return true;
}
}
// 如果移除的是叶子节点,直接置为 null
private E removeAt(int i) {
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;
}

heapify 方法

private void heapify() {
// 从 queue[size/2-1] 位置开始执行 siftDown
// 即最后一层非叶子节点开始调整位置
for (int i = (size >>> 1) - 1; i >= 0; i--)
siftDown(i, (E) queue[i]);
}

iterator 方法

优先级队列的迭代器

public Iterator<E> iterator() {
return new Itr();
}
private final class Itr implements Iterator<E> {
// next 元素的坐标
private int cursor = 0;
// 移除元素存入
private ArrayDeque<E> forgetMeNot = null;
// 最近一次获取的元素的坐标,如果元素已经被 remove 则为 -1
private int lastRet = -1;
// 最近一次从 forgetMeNot 出队列的元素
private E lastRetElt = null;
public boolean hasNext() {
return cursor < size ||
(forgetMeNot != null && !forgetMeNot.isEmpty());
}
// 先从 queue 中依次获取
public E next() {
if (cursor < size)
return (E) queue[lastRet = cursor++];
if (forgetMeNot != null) {
lastRet = -1;
// 从 forgetMeNot 队列中出队列
lastRetElt = forgetMeNot.poll();
if (lastRetElt != null)
return lastRetElt;
}
throw new NoSuchElementException();
}
public void remove() {
if (lastRet != -1) {
// 移除 lastRet
E moved = PriorityQueue.this.removeAt(lastRet);
lastRet = -1;
if (moved == null)
cursor--;
else {
if (forgetMeNot == null)
forgetMeNot = new ArrayDeque<>();
// 放入 forgetMeNot 队列
forgetMeNot.add(moved);
}
} else if (lastRetElt != null) {
PriorityQueue.this.removeEq(lastRetElt);
lastRetElt = null;
} else {
throw new IllegalStateException();
}
}
}






发布于: 2020 年 07 月 22 日 阅读数: 8
用户头像

Alex🐒

关注

还未添加个人签名 2020.04.30 加入

还未添加个人简介

评论

发布
暂无评论
【数据结构】Java 常用集合类 PriorityQueue