实现优先级队列最常用的数据结构是堆，堆的常见实现有二叉堆、斐波那契堆、二项堆等。

二叉堆

堆是一种完全二叉树，我们以小根堆为例，小根堆的性质就是，每个节点都小于其左孩子和右孩子，不难发现，这种二叉树，根的值是最小的。

堆有以下几种操作：堆的初始化、修改某个值（规定修改之后的值小于等于原来的值）、插入某个值、取出根节点（即取出该优先队列中的优先级最高的值）。

在进行这几种操作的时候，要维护堆的性质。

堆的存储

我们不难发现以下结论：在一棵完全二叉树中，假设节点下标从0开始，那么点i的左孩子的下标为 (i

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

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++;

}

本文作者：中国农业银行研发中心西安研发部 陈登帅