Binomial Queue

前面堆排序已经描述了二叉堆的基本操作，插入(O(logn))、删除(O(logn))和查询最大最小值(O(1))，但是两个二叉堆合并时却很不方便，一个一个调用插入方法完成合并需要O(n)。

Binomial Queue(二项队列)：一个链表数组，每个元素指向一棵二项树，数组元素按二项树大小顺序排列。

Binomial Tree(二项树) 是什么 图解


合并两个二项队列 图解


二项队列的插入：就是与一个单节点的堆合并。
查询最大最小：遍历链表数组一遍。
删除最小：将被删除节点的子树变为一个新的二项队列，再与原二项队列合并。

数据结构表示

typedef int ElementType;
typedef struct BinNode *Position;

struct BinNode
{
	ElementType Element;
	Position    LeftChild;
	Position    NextSibling;// not LightChild
};

typedef struct BinNode *BinTree;

struct Collection
{
	int CurrentSize;
	BinTree TheTrees[MaxTrees];
};

typedef struct Collection *BinQueue;

来自《数据结构与算法分析》