前言
我們在日常開發中時常使用到優先佇列這個結構，它可以幫助我們將添加到集合中的元素按指定的優先級排序，真是十分好用的一個結構，雖然對它底層的實作原理有些了解，但是我還是忍不住想自己動手實作一個優先佇列，
實作功能
JDK中的PriorityQueue的功能比較多，但我們的優先佇列只實作一些核心的功能：
- 泛型，支持任意元素
- 可自定義比較器，支持自定義元素的優先順序
- 物件陣列存盤元素，需實作擴容方式
- 通過堆維護元素順序
- 先進先出，非雙端佇列
- 迭代器訪問，和支持
foreach遍歷 fast-fail機制
優先級原理
優先佇列底層是通過一個物件陣列來存盤資料，但是邏輯上卻是通過堆結構來組織資料，通過維護一個小頂堆，從而實作了每次取元素都是優先級最高的，
為了維護小頂堆，向佇列寫入元素時，需要向上調整；從佇列中彈出元素時，需要向下調整，細節請看下面原始碼：
注意：堆頂在陣列頭方向，不能選擇放在隊尾，因為那樣的話，彈出堆頂然后向下調整時，陣列頭部會空出位置，
/**
* 向上調整
*
* @param i 調整的元素下標
* @param e 調整的
元素值
*/
private void siftUp(int i, E e) {
while (i > 0) {
int parent = (i - 1) >> 1;
Object p = queue[parent];
if (comparator.compare(e, (E) p) > 0)
break;
queue[i] = p;
i = parent;
}
queue[i] = e;
}
/**
* 向下調整
*
* @param i 調整的元素下標
* @param e 調整的元素值
*/
private void siftDown(int i, E e) {
int half = size >> 1; // only need to traverse non-leaf node
while (i < half) {
queue[i] = e;
int l = (i << 1) + 1, r = l + 1, g = i;
if (l < size && comparator.compare((E) queue[l], (E) queue[g]) < 0)
g = l;
if (r < size && comparator.compare((E) queue[r], (E) queue[g]) < 0)
g = r;
if (g == i)
break;
queue[i] = queue[g];
i = g;
}
queue[i] = e;
}
public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
modCount++;
int i = size;
if (i == cap)
grow();
siftUp(i, e);
size++;
return true;
}
public E poll() {
final Object result;
if ((result = queue[0]) != null) {
modCount++;
Object e = queue[--size];
queue[size] = null;
siftDown(0, (E) e);
}
return (E) result;
}
迭代器訪問
通過創建實作Iterator介面的內部類可實作迭代器訪問，如果要支持 foreach 遍歷方式，需要讓優先佇列實作Iterable類，即實作一個回傳iterator物件的方法，
實作代碼
原始碼請看GitHub倉庫：
github - MyPriorityQueue
如果訪問速度太慢，可訪問Gitee：
gitee - MyPriorityQueue
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/297253.html
標籤：Java