优先队列，堆

二叉堆

任意结点小于它的所有后裔。完全二叉树，可用数组实现，i处的左儿子在2i处，右儿子在2i+1处。
最小点或最大点总在根处，其它的关系不好得出。

基本操作

insert 上滤，新的结点放到最后面，再上滤。
deleteMin 下滤，最后一个点放到根结点，再下滤。
decreaseKey
increaseKey
remove
buildHeap 任意顺序放入树中，再从currentSize/2处点开始一直到根结点进行下滤。

缺点

不支持高效率的find和merge。

d堆

d叉树。

左式堆

左儿子的零路径长至少与右儿子的零路径长一样大。存在最短的右路径。
可以有效地支持合并，O(logN)运行时间。

操作

merge 合并，递归地将具有大的根值的堆与具有较小根值的堆的右子堆合并。调整左右两个子树，不满足条件是交换两棵子树。递归算法的完美体现。
insert 单节点的merge
deleteMin 合并剩下的两个子堆。
buildHeap 递归建立左右子树（？）

斜堆

近似于左式堆，但没有结构限制。
merge 总是交换左右儿子。合并右路径，除最后的节点外交换右路径上每个结点的左儿子和右儿子。

二项队列

堆序树的集合，且没有高度相同的树。Bk树通过把Bk-1树附接到Bk-1的根上形成。相当于二进制数中的每一位。1101表示，有B0、B2、B3三棵树。

操作

最小元： 比较各个树根
合并： 合并高度相同的两棵树，一棵接到另一棵的根结点上。若有相同的，则继续，只到没有高度相同的树。
插入： 特殊的合并。
deleteMin: 最小根的树删掉根结点，形成两棵树，再与其它的树合并。

实现

根结点保存成vector向量，每个结点保存第一个儿子和右兄弟的指针。

标准库中的优先队列

priority_queue