實現優先級隊列最常用的數據結構是堆，堆的常見實現有二叉堆、斐波那契堆、二項堆等。
二叉堆
堆是一種完全二叉樹，我們以小根堆為例，小根堆的性質就是，每個節點都小于其左孩子和右孩子，不難發現，這種二叉樹，根的值是最小的。
堆有以下幾種操作：堆的初始化、修改某個值（規定修改之后的值小于等于原來的值）、插入某個值、取出根節點（即取出該優先隊列中的優先級最高的值）。
在進行這幾種操作的時候，要維護堆的性質。
堆的存儲
我們不難發現以下結論：在一棵完全二叉樹中，假設節點下標從0開始，那么點i的左孩子的下標為 (i<<1)+1，右孩子的下標為(i<<1)+2 ，父節點的下標為(i-1)>>1，我么可以使用數組來存儲這棵完全二叉樹。
向下調整
向下調整即調整某個子樹成為小根堆，由于小根堆的任意一個子樹必定也是小根堆，當我們修改了位于i節點的某個值的時候，假設修改的值不小于原來的值，或者說修改的是根節點，那么如果要保持小根堆的性質，那么必定要判斷這個節點是否需要移動，如果需要移動，那么必定是會移動到其子樹中，不會向上移動。
所以這時候就要將這個節點和它的兩個孩子中的值較小的進行交換，由于完全二叉樹的性質，右子樹的深度總是小于等于左子樹，所以為了這一小點優勢，我們通常在兩個孩子值相同時，和右孩子交換，然后這時候和他交換的這個孩子又需要調整了，顯然也需要向下調整，因此我們遞歸調用向下調整，直到沒有交換，或者到了葉子節點。這個操作的時間復雜度為O (lgn) 。
向上調整
向上調整和向下調整一樣，適合將某個節點的值改為比以前更小或者相等的值，或者修改了葉子節點的情況。
在這兩種情況下，該節點需要向上移動，就是直接和這個節點的父節點比較，如果比父節點還小，那么就和他的父節點交換，然后遞歸向上調整它的父節點，直到到達根節點，或者某次沒有交換。這個操作的復雜度也是O(logn)。
初始化
完全二叉樹的一個顯而易見的性質，假設其標號從0開始，到n-1結束，那么從n/2到n-1的點全是葉子節點，葉子節點可以看成是節點數為1的堆，所以說我們如果要構建一個堆，就從(n/2)-1到0點進行向下調整即可。
初始化的時間復雜度乍一看是O(nlogn) ，調整n/2次，每次復雜度是O (logn)，這不是O (nlogn) 嗎？其實不然，調整n/2次不假，但是并不是每次調整都是O (logn) ，因為每次調整的復雜度取決于調整的子樹的高度。
因此，其復雜度小于O (nlogn) ，實際上初始化堆的時間復雜度為O (n) 。
修改某值
假設把下標為i的節點的值改為了key（修改之后的值比之前的小，也就是優先級更高），那么如果要維護堆的性質，就要在該節點處向上調整。該操作的時間復雜度為O (logn)。
插入某值
將新節點插入到末尾，這個新節點必定是葉子節點，那么直接在這個節點上向上調整即可。該操作的時間復雜度為O (logn) 。
獲取優先級最高的值并刪除
由于二叉堆的性質，根節點的優先級必定是最高的（即節點的值最小）所以獲取優先級最高的值只需要將根節點返回即可，如果要刪除掉該節點，那么就將最后一個節點放到根節點的位置，然后從根節點處向下調整即可。該操作的時間復雜度為O(logn) 。
二叉堆實現代碼
import JAVA.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Heap> {
//堆的規模
private int n;
//具體的堆
private List a;
public Heap(T[] a) {
this.a = new ArrayList<>();
this.a.addAll(Arrays.asList(a));
this.n = this.a.size();
build();
* 初始化堆
public void build() {
for (int i = (n >> 1) - 1; i >= 0; i--) {
down(i);
* 獲取父節點的下標
* @param i
* @return
private int parent(int i) {
return (i-1)>>1;
* 獲取左孩子的下標
* @param i
* @return
public int left(int i) {
return (i << 1) + 1;
* 獲取右孩子的下標
* @param i
* @return
public int right(int i) {
return (i << 1) + 2;
* 向下調整，以滿足小根堆的性質
* @param i
public void down(int i) {
int left = left(i);
int right = right(i);
int small = i;
if (left < n && a.get(left).compareTo(a.get(i)) < 0) {
small = left;
if (right < n && a.get(right).compareTo(a.get(small)) < 0) {
small = right;
if (small != i) {
T temp = a.get(i);
a.set(i, a.get(small));
a.set(small, temp);
down(small);
* 向上調整
* @param i
public void up(int i) {
int parent = parent(i);
if (parent >= 0 && a.get(parent).compareTo(a.get(i)) > 0) {
T temp = a.get(i);
a.set(i, a.get(parent));
a.set(parent, temp);
up(parent);
* 將下標為i處的節點值更新為key（變小）
* @param i
* @param key
public void update(int i, T key) {
a.set(i, key);
up(i);
* 插入新的節點key
* @param key
public void insert(T key) {
a.add(key);
n++;
up(n - 1);
* 獲取并移除根節點
* @return
public T getTop() {
T result = a.get(0);
a.set(0, a.get(--n));
down(0);
return result;
@Override
public String toString() {
return a.toString();
public static void main(String[] args) {
Integer[] a = {16, 4, 10, 14, 7, 9, 3, 2, 8, 1};
Heap heap = new Heap<>(a);
System.out.println(heap);
heap.insert(13);
System.out.println(heap);
heap.update(3, 1);
System.out.println(heap);
斐波那契堆
斐波那契堆(Fibonacci heap)是堆中一種，它和二項堆一樣，也是一種可合并堆，可用于實現合并優先隊列。斐波那契堆比二項堆具有更好的平攤分析性能，它的合并操作的時間復雜度是O (1) 。
與二項堆一樣，它也是由一組堆最小有序樹組成，并且是一種可合并堆。與二項堆不同的是，斐波那契堆中的樹不一定是二項樹，而且二項堆中的樹是有序排列的，但是斐波那契堆中的樹都是有根而無序的。
基本定義
typedef int Type;
typedef struct _FibonacciNode
Type key; // 關鍵字(鍵值)
int degree; // 度數
struct _FibonacciNode *left; // 左兄弟
struct _FibonacciNode *right; // 右兄弟
struct _FibonacciNode *child; // 第一個孩子節點
struct _FibonacciNode *parent; // 父節點
int marked; //是否被刪除第1個孩子(1表示刪除，0表示未刪除)
}FibonacciNode, FibNode;
FibNode是斐波那契堆的節點類，它包含的信息較多。key是用于比較節點大小的，degree是記錄節點的度，left和right分別是指向節點的左右兄弟，child是節點的第一個孩子，parent是節點的父節點，marked是記錄該節點是否被刪除第1個孩子(marked在刪除節點時有用)。
typedef struct _FibonacciHeap{
int keyNum; // 堆中節點的總數
int maxDegree; // 最大度
struct _FibonacciNode *min; // 最小節點(某個最小堆的根節點)
struct _FibonacciNode **cons; // 最大度的內存區域
}FibonacciHeap, FibHeap;
FibHeap是斐波那契堆對應的類。min是保存當前堆的最小節點，keyNum用于記錄堆中節點的總數，maxDegree用于記錄堆中最大度，而cons在刪除節點時來暫時保存堆數據的臨時空間。
從圖中可以看出，斐波那契堆是由一組小根堆組成，這些小根堆的根節點組成了雙向鏈表(根鏈表)，斐波那契堆中的最小節點就是"根鏈表中的最小節點"！
基本操作
插入操作
插入操作非常簡單：插入一個節點到堆中，直接將該節點插入到"根鏈表的min節點"之前即可；若被插入節點比"min節點"小，則更新"min節點"為被插入節點。
斐波那契堆的根鏈表是"雙向鏈表"，這里將min節點看作雙向聯表的表頭。在插入節點時，每次都是"將節點插入到min節點之前(即插入到雙鏈表末尾)"。
此外，對于根鏈表中小根堆都只有一個節點的情況，插入操作就很演化成雙向鏈表的插入操作。
* 將"單個節點node"加入"鏈表root"之前
* a …… root
* a …… node …… root
* 注意： 此處node是單個節點，而root是雙向鏈表
static void fib_node_add(FibNode *node, FibNode *root)
node->left = root->left;
root->left->right = node;
node->right = root;
root->left = node;
* 將節點node插入到斐波那契堆heap中
static void fib_heap_insert_node(FibHeap *heap, FibNode *node)
if (heap->keyNum == 0)
heap->min = node;
else
fib_node_add(node, heap->min);
if (node->key < heap->min->key)
heap->min = node;
heap->keyNum++;
本文作者：中國農業銀行研發中心西安研發部 陳登帥
