Java集合(一) —— Collection源碼分析
Java集合(二) —— ArrayList源碼分析
Java集合(三) —— LinkedList源碼分析
Java集合(四) —— PriorityQueue源碼分析
Java集合(五) —— HashSet源碼分析
Java集合(六) —— LinkedHashSet源碼分析
Java集合(七) —— TreeSet源碼分析
Java集合(八) —— HashMap源碼分析
Java集合(九) —— LinkedHashMap源碼分析
Java集合(十) —— TreeMap源碼分析
1.PriorityQueue繼承關系圖
PriorityQueue.png
2數據結構
// 數組
transient Object[] queue;
1.優(yōu)先隊列并不是按照FIFO進行數據操作的，其數據具有優(yōu)先級刹帕，優(yōu)先級高的元素先出隊吵血。優(yōu)先隊列是基于小頂堆(堆排序的一種)原理實現(xiàn)的。
2.堆：堆是一個樹型結構偷溺，是一棵完全二叉樹蹋辅。完全二叉樹是一層一層按照進入的順序排列的。按照這個特性可以使用數組按照完全二叉樹實現(xiàn)堆挫掏。
1469176-20190329000534658-1905270280.png
3.堆排序：利用堆這種數據結構所設計的一種排序算法侦另。
- 大頂堆：根節(jié)點的值最大。子節(jié)點一定小于或等于父節(jié)點尉共。
- 小頂堆：根節(jié)點的值最小褒傅。子節(jié)點一定大于或等于父節(jié)點。(Java中的優(yōu)先隊列(PriorityQueue)是基于小頂堆實現(xiàn)的袄友。)
4.堆排序思想：
- 構建初始堆殿托，將待排序序列構成一個大頂堆或小頂堆。
- 將堆頂元素與堆尾元素交換剧蚣，并斷開(從待排序列中移除)堆尾元素支竹。
- 重復構建堆旋廷。
- 重復2~3，直到待排序列只剩一個元素(堆頂元素)唾戚。
3.性能分析
優(yōu)先隊列初始化堆時柳洋，其時間復雜度為O(n)；（怎樣才是一個初始化好的堆叹坦？要求子節(jié)點不大于/不小于父節(jié)點熊镣，但是不要求是完全排好序的）
入隊和出隊時只是調整堆結構，并不需要將所有元素排序募书，其時間復雜度為O(log2n)（具體計算另行百度）绪囱。
4.源碼分析
1.成員變量
// 數組默認容量
private static final int DEFAULT_INITIAL_CAPACITY = 11;
// 數據結構為數組
transient Object[] queue;
// 數組大小
private int size = 0;
// 比較器
private final Comparator<? super E> comparator;
// 修改次數
transient int modCount = 0;
2.構造方法
public PriorityQueue() {
this(DEFAULT_INITIAL_CAPACITY, null);
}
// 指定初始容量
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) {
if (initialCapacity < 1)
throw new IllegalArgumentException();
this.queue = new Object[initialCapacity];
this.comparator = comparator;
}
// 使用集合構建優(yōu)先隊列
@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);
}
}
@SuppressWarnings("unchecked")
public PriorityQueue(PriorityQueue<? extends E> c) {
this.comparator = (Comparator<? super E>) c.comparator();
initFromPriorityQueue(c);
}
@SuppressWarnings("unchecked")
public PriorityQueue(SortedSet<? extends E> c) {
this.comparator = (Comparator<? super E>) c.comparator();
initElementsFromCollection(c);
}
3.常用方法
- 新增元素
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 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];
// 新增元素與父節(jié)點元素比較(默認小頂堆莹捡，最小元素為根節(jié)點)
if (key.compareTo((E) e) >= 0)
// 新增元素大于父節(jié)點元素鬼吵，則跳出循環(huán)，不用調整堆的結構
break;
// 否則需要調整堆的結構篮赢，循環(huán)調整元素的位置
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;
}
關于擴容
private void grow(int minCapacity) {
int oldCapacity = queue.length;
// 擴容機制齿椅，容量小于64時，新容量 = 舊容量*2+2启泣；大于64時涣脚，新容量 = 舊容量 + 舊容量 >> 1
int newCapacity = oldCapacity + ((oldCapacity < 64) ?
(oldCapacity + 2) :
(oldCapacity >> 1));
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 數組復制
queue = Arrays.copyOf(queue, newCapacity);
}
2.移除隊列頭元素
/**
* 移除隊列頭元素，內部調用了poll方法寥茫，如果隊列為空則拋出異常
*/
public E remove() {
E x = poll();
if (x != null)
return x;
else
throw new NoSuchElementException();
}
/**
* 移除隊列頭元素遣蚀，如果隊列為空，則返回null
*/
@SuppressWarnings("unchecked")
public E poll() {
if (size == 0)
return null;
// 數組大小-1
int s = --size;
modCount++;
// 獲取隊列第一個元素
E result = (E) queue[0];
// 獲取隊列最后一個元素
E x = (E) queue[s];
// 將數組最后一個元素置為null
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);
}
@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; // 左子樹
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;
}
3.獲取隊列頭元素
/**
* 獲取隊列頭元素芭梯，內部調用了peek方法，如果隊列為空則拋出異常
*/
public E element() {
E x = peek();
if (x != null)
return x;
else
throw new NoSuchElementException();
}
/**
* 獲取隊列頭元素弄喘，如果隊列為空則返回null
*/
public E peek() {
return (size == 0) ? null : (E) queue[0];
}
5.總結
- PriorityQueue優(yōu)先隊列玖喘，不適合一些經常出隊入隊的場景，但是他的優(yōu)先級特性非常適合一些對順序有要求的數據處理場景蘑志。
- 堆（完全二叉樹）的數據結構不難理解芒涡，但是在優(yōu)先隊列中，出隊和入隊都可能引起堆結構的調整(實際上就是數組元素位置的調整)卖漫，調整算法有點晦澀難懂，有興趣的朋友可以好好了解該算法的實現(xiàn)赠群。
- 優(yōu)先隊列在工作中的場景比較有限（至少我工作中沒有使用過）羊始，不喜歡的可以略過。
