原文鏈接http://zhhll.icu/2021/01/08/java%E5%9F%BA%E7%A1%80/%E9%9B%86%E5%90%88/PriorityQueue%E8%AF%A6%E8%A7%A3/
PriorityQueue詳解
PriorityQueue是優先級佇列，底層使用陣列存盤，是基于二叉堆的一個無界佇列，可以使用默認排序或者提供Comparator比較器使得佇列中的元素有序
存盤結構
小頂堆
根節點的元素最小是小頂堆(小于左右子節點的值)
graph TD 0((0)) --- 1((1)) --- 3((3)) 1((1)) --- 4((4)) 0((0)) --- 2((2))大頂堆
根節點的元素最大是大頂堆(大于左右子節點的值)
graph TD 0((4)) --- 1((3)) --- 3((1)) 1((3)) --- 4((0)) 0((4)) --- 2((2))原始碼分析
重要屬性
// 默認的初始容量
private static final int DEFAULT_INITIAL_CAPACITY = 11;
/**
* 使用陣列存放 是一個平衡二叉堆，對于queue[n]有兩個子節點queue[2*n+1] 和 queue[2*(n+1)]
*/
transient Object[] queue; // non-private to simplify nested class access
/**
* 優先佇列中的元素個數
*/
private int size = 0;
/**
* 比較器，如果為null，為使用默認的自然排序
*/
private final Comparator<? super E> comparator;
/**
* 修改次數
*/
transient int modCount = 0; // non-private to simplify nested class access
/**
* 最大容量
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
構造器
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) {
// 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;
}
@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);
}
常用方法
獲取頂端元素
// 直接取陣列中的第一個元素就是頂端元素
public E peek() {
return (size == 0) ? null : (E) queue[0];
}
插入
以使用默認比較器為例
// 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;
}
// 傳入的minCapacity為插入該資料所需要的最小容量
private void grow(int minCapacity) {
int oldCapacity = queue.length;
// 如果原始容量小于64，則容量加2，否則容量增加50%
int newCapacity = oldCapacity + ((oldCapacity < 64) ?
(oldCapacity + 2) :
(oldCapacity >> 1));
// overflow-conscious code
if (newCapacity - MAX_ARRAY_SIZE > 0)
// 如果擴容之后的容量大于MAX_ARRAY_SIZE,則比較所需要的容量和MAX_ARRAY_SIZE的大小
//(minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
newCapacity = hugeCapacity(minCapacity);
queue = Arrays.copyOf(queue, newCapacity);
}
private void siftUp(int k, E x) {
if (comparator != null) // 使用自定義選擇器
siftUpUsingComparator(k, x);
else // 使用默認的自然排序，默認的排序為小頂堆
siftUpComparable(k, x);
}
// 存放資料的核心代碼
// k為所要存放的索引位置，x為元素
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索引位置
k = parent; // 索引位置變成父節點的索引位置，繼續對比父節點的父節點
}
queue[k] = key;
}
洗掉
還是以默認的比較器為例
public boolean remove(Object o) {
// 找到該物件對應的索引位置
int i = indexOf(o);
if (i == -1)
return false;
else {
removeAt(i);
return true;
}
}
// 找到該物件對應的索引位置
private int indexOf(Object o) {
if (o != null) {
for (int i = 0; i < size; i++)
if (o.equals(queue[i]))
return i;
}
return -1;
}
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);
// 沒有進while回圈時(表示在siftDown()方法中直接走到queue[k] = key;),洗掉節點沒有子節點，開始向上查找
// 向上查找的原因是因為可能所洗掉的節點與尾結點處于不同的子樹下
if (queue[i] == moved) {
siftUp(i, moved);
if (queue[i] != moved)
return moved;
}
}
return null;
}
// k為所要洗掉的元素位置 x為尾結點元素
private void siftDown(int k, E x) {
if (comparator != null)
siftDownUsingComparator(k, x);
else
siftDownComparable(k, x);
}
// 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;
}
//跳出回圈的條件是尾結點元素大于子節點元素了，所以將尾結點元素放到k索引位置
queue[k] = key;
}
// k為要洗掉的索引位置 x為尾結點元素
private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x);
}
// k為要洗掉的索引位置 x為尾結點元素
// 從洗掉索引位置開始向上查找
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;
}
由于本身的博客百度沒有收錄，博客地址http://zhhll.icu
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/255045.html
標籤：Java
下一篇：Java基礎之：泛型