前言
PriorityQueue是優(yōu)先隊列, 也就是說在隊列中的元素是有優(yōu)先級的, 優(yōu)先級高的元素會先出隊列.
本文源碼: 本文源碼下載
例子
先以一個簡單的例子來了解一下
PriorityQueue的簡單用法.
package com.priorityqueue;
import java.util.Comparator;
public class Test01 {
public static void main(String[] args) {
PriorityQueue<Integer> pq = new PriorityQueue<>(10, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1 - o2;
}
});
pq.add(1);
pq.add(3);
pq.add(2);
pq.add(0);
while (!pq.isEmpty()) {
System.out.print(pq.poll() + " ");
}
}
}
輸出如下: 可以看到輸出結(jié)果并不是按加入的順序輸出,而是按照優(yōu)先級大小輸出的.
0 1 2 3
源碼
屬性
// 默認(rèn)隊列容量大小
private static final int DEFAULT_INITIAL_CAPACITY = 11;
/**
* 存儲元素用的數(shù)組
*/
transient Object[] queue; // non-private to simplify nested class access
/**
* 當(dāng)前隊列中元素的個數(shù)
*/
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
構(gòu)造函數(shù)
public PriorityQueue(int initialCapacity) {
this(initialCapacity, null);
}
public PriorityQueue(Comparator<? super E> comparator) {
this(DEFAULT_INITIAL_CAPACITY, comparator);
}
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;
}
加入元素
/**
* 將元素e加入到優(yōu)先隊列中
* 以下情況下會報異常:
* 1. e為null會拋出NullPointerException異常
* 2. e無法比較會拋出ClassCastException異常
* 3. 容量達(dá)到極限拋出OutofMemoryException異常
*
* @return {@code true} (as specified by {@link Collection#add})
* @throws ClassCastException if the specified element cannot be
* compared with elements currently in this priority queue
* according to the priority queue's ordering
* @throws NullPointerException if the specified element is null
*/
public boolean add(E e) {
return offer(e);
}
/**
* 將元素e加入到優(yōu)先隊列中
* 以下情況下會報異常:
* 1. e為null會拋出NullPointerException異常
* 2. e無法比較會拋出ClassCastException異常
* 3. 容量達(dá)到極限拋出OutofMemoryException異常
* @return {@code true} (as specified by {@link Queue#offer})
* @throws ClassCastException if the specified element cannot be
* compared with elements currently in this priority queue
* according to the priority queue's ordering
* @throws NullPointerException if the specified element is null
*/
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;
}
可以看到最終調(diào)用的是
siftUp(i, e)方法, 接下來看看該方法是如何實現(xiàn)的.
private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x);
}
@SuppressWarnings("unchecked")
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;
}
@SuppressWarnings("unchecked")
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;
}
看著代碼可能不那么好理解, 接下來以一個例子來輔助理解這段代碼.
圖片.png
上圖是一個優(yōu)先隊列,藍(lán)色字代表該節(jié)點對應(yīng)的數(shù)組下標(biāo), 對應(yīng)的數(shù)組如下:
圖片.png
可以看到堆是一個完全二叉樹, 如果一個節(jié)點的下標(biāo)是
i, 則該節(jié)點的父親節(jié)點下標(biāo)是(i - 1) / 2, 根節(jié)點下標(biāo)是0.
現(xiàn)在看看往堆中增加一個元素
2是如何操作的.
圖片.png
最終用數(shù)組的表現(xiàn)形式如下:
圖片.png
消費元素
@SuppressWarnings("unchecked")
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;
}
同樣的道理該方法的重點還是在
siftDown, 思路是取出下標(biāo)為0的節(jié)點并且保存最后一個節(jié)點的元素, 相當(dāng)于把最后一個節(jié)點放到下標(biāo)為0的位置, 因為有可能此操作會導(dǎo)致堆的性質(zhì)被破壞, 所以需要利用siftDown來維持堆的性質(zhì).
private void siftDown(int k, E x) {
if (comparator != null)
siftDownUsingComparator(k, x);
else
siftDownComparable(k, x);
}
@SuppressWarnings("unchecked")
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;
}
@SuppressWarnings("unchecked")
private void siftDownUsingComparator(int k, E x) {
int half = size >>> 1;
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];
if (comparator.compare(x, (E) c) <= 0)
break;
queue[k] = c;
k = child;
}
queue[k] = x;
}
相對于
siftUp需要去找到parent,siftDown則需要去找到兩個child, 如果當(dāng)前節(jié)點的下標(biāo)是i, 那此節(jié)點的左孩子節(jié)點下標(biāo)為2 * i + 1, 右孩子下標(biāo)為2 * i + 2.
以下也是通過一個小例子來解析該代碼要做的事情.
圖片.png
對應(yīng)的數(shù)組表示如下:
圖片.png
刪除元素
/** 返回值：(遍歷的時候會用到)
* 如果往下調(diào)整 則返回null
* 如果往上調(diào)整 則需要返回被調(diào)整的moved值
*
*/
@SuppressWarnings("unchecked")
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;
siftDown(i, moved);
if (queue[i] == moved) {
siftUp(i, moved);
if (queue[i] != moved)
return moved;
}
}
return null;
}
可以看到該方法是刪除在下標(biāo)
i的元素, 如果是最后一個元素可以直接刪除而不會影響堆的性質(zhì), 如果不是則需要先模擬刪除最后一個元素然后把該元素插入到i的位置, 因為此時不知道放到i這個位置是對堆的結(jié)構(gòu)上面有影響還是下側(cè)有影響, 因此就先通過往下調(diào)整來嘗試, 如果往下調(diào)整成功則不需要往上調(diào)整, 否則需要繼續(xù)往上調(diào)整.
遍歷元素
遍歷元素
Iterator的本質(zhì)作用就是遍歷整個元素,在遍歷的過程中可通過iterator.remove()來刪除元素.
先通過一個例子來看看如何工作的.
package com.priorityqueue;
import java.util.Comparator;
import java.util.Iterator;
public class Test02 {
public static void main(String[] args) {
PriorityQueue<Integer> pq = new PriorityQueue<>(10, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1 - o2;
}
});
pq.add(1);
pq.add(3);
pq.add(12);
pq.add(4);
pq.add(6);
pq.add(17);
pq.add(13);
pq.add(8);
pq.add(5);
pq.add(10);
pq.add(11);
pq.add(19);
pq.add(23);
pq.add(14);
System.out.println(pq);
Iterator<Integer> iter = pq.iterator();
while (iter.hasNext()) {
int val = iter.next();
//if (val == 23) iter.remove();
System.out.print(val + " ");
}
}
}
輸出如下: 正常輸出.
[1, 3, 12, 4, 6, 17, 13, 8, 5, 10, 11, 19, 23, 14]
1 3 12 4 6 17 13 8 5 10 11 19 23 14
那如果在遍歷過程中如果刪除元素會怎么樣呢掌敬？把上文代碼中打開刪除元素
23. 可以得知在刪除過程中需要調(diào)整整個堆的結(jié)構(gòu),也就疑問著原有結(jié)構(gòu)會產(chǎn)生變化. 至于會產(chǎn)生什么變化, 看下圖.
圖片.png
可以看到當(dāng)
Iterator遍歷到23時, 然后刪除23節(jié)點時, 會調(diào)整到右側(cè)的圖結(jié)構(gòu), 可以看到調(diào)整后14節(jié)點所在的位置也就被遍歷過了,14這個節(jié)點是如何被遍歷的呢?
答案是在刪除的過程中如果是需要向上調(diào)整時最后的一個元素(比如
14)可能會被調(diào)整到一個被已經(jīng)遍歷過的位置(下標(biāo)5), 但是會有一個ArrayDeque對象來加入到這個節(jié)點,等到正常順序遍歷完后會從ArrayDeque對象取元素. 當(dāng)向下調(diào)整時就沒有必要加入到ArrayDeque對象中,因為下面的元素都還沒有被遍歷過.
public Iterator<E> iterator() {
return new Itr();
}
private final class Itr implements Iterator<E> {
/**
* 當(dāng)前遍歷到元素下標(biāo)
*/
private int cursor = 0;
/**
* 上個被遍歷的元素下標(biāo)
*/
private int lastRet = -1;
/**
* 存放因為刪除元素而導(dǎo)致被替換到已經(jīng)被遍歷過的下標(biāo)所在的位置上
* 放到正常遍歷結(jié)束后再取這里所有的元素
*/
private ArrayDeque<E> forgetMeNot = null;
/**
* 在遍歷forgetMeNot時上個遍歷元素
*/
private E lastRetElt = null;
/**
* The modCount value that the iterator believes that the backing
* Queue should have. If this expectation is violated, the iterator
* has detected concurrent modification.
*/
private int expectedModCount = modCount;
public boolean hasNext() {
return cursor < size ||
(forgetMeNot != null && !forgetMeNot.isEmpty());
}
@SuppressWarnings("unchecked")
public E next() {
if (expectedModCount != modCount)
throw new ConcurrentModificationException();
if (cursor < size) //正常遍歷情況
return (E) queue[lastRet = cursor++];
if (forgetMeNot != null) { // 從forgetMeNot中取元素
//System.out.println("in forgetMeNot != null next()");
lastRet = -1;
lastRetElt = forgetMeNot.poll();
if (lastRetElt != null)
return lastRetElt;
}
throw new NoSuchElementException();
}
public void remove() {
if (expectedModCount != modCount)
throw new ConcurrentModificationException();
if (lastRet != -1) { // 正常遍歷過程中刪除元素
/**
* moved為null 表明是不會影響遍歷情況
* 否則需要加入到ArrayDeque留作后續(xù)遍歷 因為該元素被調(diào)整到之前已經(jīng)被遍歷的下標(biāo)位置了
*/
E moved = PriorityQueue.this.removeAt(lastRet);
lastRet = -1;
if (moved == null)
cursor--;
else {
if (forgetMeNot == null)
forgetMeNot = new ArrayDeque<>();
//System.out.println("forgetMeNot add moved:" + moved);
forgetMeNot.add(moved);
}
} else if (lastRetElt != null) { // 遍歷ArrayDeque過程中刪除元素
PriorityQueue.this.removeEq(lastRetElt);
lastRetElt = null;
} else {
throw new IllegalStateException();
}
expectedModCount = modCount;
}
}
擴容
因為
PriorityQueue是被設(shè)計成無界的,所以當(dāng)元素越來越多時需要進(jìn)行擴大容量. 代碼比較簡單就不多說了.
參考
1.
Java1.8源碼
