在二叉堆上可以进行插入节点、删除节点、取出值最小的节点、减小节点的值等基本操作。

形式上看，它从顶点开始，每个节点有两个子节点，每个子节点又各自有自己的两个子节点;数值上看，每个节点的两个子节点都比它大或和它相等。

在二叉堆里我们要求:

* 最小的元素在顶端

* 每个元素都比它的父节点大，或者和父节点相等。

只要满足这两个条件，其他的元素怎么排都行。如上面的例子，最小的元素10在最顶端，第二小的元素20在10的下面，但是第三小的元素24在20的下面，也就是第三层，更大的30反而在第二层。

这样一"堆"东西我们在程序中怎么用呢?幸运的是，二叉堆可以用一个简单的一维数组来存储，如下图所示。

假设一个元素的位置是n(第一个元素的位置为1，而不是通常数组的第一个索引0)，那么它两个子节点分别是 n × 2 和 n × 2 + 1 ，父节点是n除以2取整。比如第3个元素(例中是20)的两个子节点位置是6和7(空)，父节点位置是1。

对于二叉堆我们通常有三种操作:添加、删除和修改元素:

* 添加元素

首先把要添加的元素加到数组的末尾，然后和它的父节点(位置为当前位置减去1再除以2取整(k-1)/2，比如第4个元素的父节点位置是1，第7个元素的父节点位置是3)比较，如果新元素比父节点元素大则交换这两个元素，然后再和新位置的父节点比较，直到它的父节点不再比它小，或者已经到达顶端，即第1的位置。

* 删除元素

删除元素的过程类似，只不过添加元素是"向上冒"，而删除元素是"向下沉":删除位置1的元素，把最后一个元素移到最前面，然后和它的两个子节点比较，如果两个子节点中较大的子节点大于此顶点，就将它们交换，直到两个子节点都比此顶点小。

计算两个子节点的位置的公式:左子节点:2K+1、右子节点:2K+2(注:这里针对的是根节点为零的情况，若根为1，则左右分别为2K与2K+1。

比如顶点为0，那么它的左右子节点分别为1和2位置，如果顶点为1，那么 1的左右两个子节点即为3，4.以此类推

* 修改元素

和添加元素完全一样的"向上冒"过程，只是要注意被修改的元素在二叉堆中的位置。

可以看出，使用二叉堆只需很少的几步就可以完成排序，很大程度上提高了寻路速度。

在C++的STL中提供了优先队列，定义方式为priority_queuepriq;默认为每一次弹出队列中最大的元素，与二叉堆性质相似，很多时候可以直接当作二叉堆使用。

当然，也可以直接自己写一个C++的类模板，以下是完整代码:

#include

const int MAXN = 11111;

int n, a[MAXN], ans = 0;

//以下两个是自定义校验函数，mincmp是小根堆所需要的，而maxcmp就是大根堆所需要的了，

inline bool mincmp(const int &x, const int &y)

{ return x < y; }

inline bool maxcmp(const int &x, const int &y)

{ return x > y; }

//定义，第一个关键字为堆的大小，第二关键字为自定义校验类型

template

class Heap

{

private:

int a[N], n;//n表示当前元素的个数，同时也是最后一个元素的下一个指针

public:

inline Heap() { clear(); }

inline void clear() { n = 0; }//清空

inline void push(int x)//插入操作

{

int i;

n++;//元素个数相加

for(i = n - 1; i > 0; i = (i - 1) >> 1)//把这个元素和根节点比较并交换

{

if(cmp(x, a[(i - 1) >> 1]))

a[i] = a[(i - 1) >> 1];

else break;

}

a[i] = x;

}

inline void pop()//弹出操作，如果需要在弹出的同时返回总根节点，把void改成int，并加上下面的两行被注释部分

{

int tmp, i;

n--;

//int x = a[0];

for(i = 0; (i << 1) + 1 < n; i = tmp)

{

//比较左右子树中更优的一个交换(对于小根堆就是较小的那个，大根堆不解释……)

tmp = ((i << 1) + 2 < n && cmp(a[(i << 1) + 2], a[(i << 1) + 1])) ? (i << 1) + 2 : (i << 1) + 1;

if(cmp(a[tmp], a[n]))

a[i] = a[tmp];

else

break;

}

a[i] = a[n];

//return x;

}

inline int top() { return a[0]; }//返回堆顶元素

inline bool empty() { return !n; }//判断堆是否为空

};

Heap< MAXN, maxcmp > h;//定义一个堆，这里定义的是大根堆，如果要使用小根堆，把第二关键字换成上面的mincmp就可以了

int main()

{

scanf("%d", &n);

for (int i = 1; i <= n; i++)

{

scanf("%d", a + i);

h.push(a[i]);//压入堆中

}

for (int i = 1; i <= n; i++)

{

printf("%d ", h.top());//从大到小输出

h.pop();

}

return 0;

}

二叉堆一般用数组来表示。例如，根节点在数组中的位置是0，第n个位置的子节点分别在2n+1和 2n+2。因此，第0个位置的子节点在1和2，1的子节点在3和4。以此类推。这种存储方式便於寻找父节点和子节点。

如下图的两个堆:

1 11

/ \ / \

2 3 9 10

/ \ / \ / \ / \

4 5 6 7 5 6 7 8

/ \ / \ / \ / \

8 9 10 11 1 2 3 4

将这两个堆保存在以1开始的数组中:

位置: 1 2 3 4 5 6 7 8 9 10 11

左图: 1 2 3 4 5 6 7 8 9 10 11

右图: 11 9 10 5 6 7 8 1 2 3 4

优先队列在信息学竞赛中十分常见，在统计问题、最值问题、模拟问题和贪心问题等等类型的题目中，优先队列都有着广泛的应用。二叉堆是一种常用的优先队列，它编程简单，效率高，但如果问题需要对两个优先队列进行合并，二叉堆的效率就无法令人满意了。本文介绍的左偏树，可以很好地解决这类问题。

左偏树的定义和性质

在介绍左偏树之前，我们先来明确一下优先队列和可并堆的概念。

优先队列，可并堆

优先队列(Priority Queue)是一种抽象数据类型(ADT)，它是一种容器，里面有一些元素，这些元素也称为队列中的节点(node)。优先队列的节点至少要包含一种性质:有序性，也就是说任意两个节点可以比较大小。为了具体起见我们假设这些节点中都包含一个键值(key)，节点的大小通过比较它们的键值而定。优先队列有三个基本的操作:插入节点(Insert)，取得最小节点(Minimum) 和删除最小节点(Delete-Min)。

可并堆(Mergeable Heap)也是一种抽象数据类型，它除了支持优先队列的三个基本操作(Insert, Minimum,Delete-Min)，还支持一个额外的操作--合并操作: