二项堆(Binomial Heap)

二项堆的定义和性质

在二叉堆(Binary Heap)的基础上，我们可以实现在可以在 $O(n)$ 时间内实现 $n$ 个结点的插入建堆操作，而之前讨论的左式堆和斜堆不可以

根据二项堆的性质，我们有以下结论：

二项树的节点数目：$B_k$ 的二项树具有 $2^k$ 个节点，这可以由递推很容易证明

在深度为$d$处的节点数恰好就是二项系数$\begin{pmatrix} k \\ d \end{pmatrix}$

二项堆的操作

Findmin

直接遍历所有树,注意到对于一个有$n$个结点的二项堆，最多有$\log n$棵树，因此时间复杂度为$O(\log n)$

也可以通过专门记录最小的节点来实现$O(1)$的时间复杂度，当然在DeleteMin的时候需要重新找到最小的节点并更新

Insert & merge

插入是特殊的合并操作，我们可以将一个新的节点看作是一个只有一个节点的二项堆，然后将其与原来的二项堆合并即可；

合并操作的过程十分类似二进制数的加法，例如一个二项堆有$B_3,B_2,B_0$,其二进制表示为$1101$，另一个二项堆有$B_3,B_1,B_0$，其二进制表示为$1011$，我们可以将其看作是二进制数相加，然后将进位的部分合并得到新的二进制数$11000$,则新的二项堆为$B_4,B_3$，我们需要保证堆的存储顺序是按高度从小到大来排列，这样时间复杂度就是$O(\log n)$

对于从空开始插入建堆的时间复杂度我们需要做特殊的分析。因为我们是要平均时间的最坏情况，事实上也就是摊还代价。

二项堆的代码实现

因为每个结点的孩子数量可能不只有2个，因此我们使用LeftChild和NextSibling的组合实现。直观上来看用LeftChild和NextSibling是让二项树翻转了：原先是根的子树从左到右高度依次增大，现在依次减小了。并且为了方便索引每棵二项树，我们用一个数组存储每棵二项树的根，其中数组的索引就对应二项树的高度

结构定义

typedef struct BinNode *Position;//指针
typedef struct Collection *BinQueue;//二项队列
typedef struct BinNode *BinTree;  //二项树

struct BinNode 
{ 
	ElementType	    Element;
	Position	    LeftChild;
	Position 	    NextSibling;
} ;

struct Collection 
{ 
	int	    	CurrentSize;  /* total number of nodes */
	BinTree	TheTrees[ MaxTrees ];//存储每棵二项树的根
} ;

合并大小相同的树($O(1)$复杂度)

BinTree
CombineTrees( BinTree T1, BinTree T2 )
{  /* merge equal-sized T1 and T2 */
	if ( T1->Element > T2->Element )
		/* attach the larger one to the smaller one */
		return CombineTrees( T2, T1 );
	/* insert T2 to the front of the children list of T1 */
	T2->NextSibling = T1->LeftChild;
	T1->LeftChild = T2;
	return T1;
}

Merge

BinQueue  Merge( BinQueue H1, BinQueue H2 )
{	BinTree T1, T2, Carry = NULL; 	
	int i, j;
	if ( H1->CurrentSize + H2-> CurrentSize > Capacity )  ErrorMessage();
	H1->CurrentSize += H2-> CurrentSize;
	for ( i=0, j=1; j<= H1->CurrentSize; i++, j*=2 ) {
	    T1 = H1->TheTrees[i]; T2 = H2->TheTrees[i]; /*current trees */
	    switch( 4*!!Carry + 2*!!T2 + !!T1 ) { 
		case 0: /* 000 */  break;
	 	case 1: /* 001 */  break;	
		case 2: /* 010 */  H1->TheTrees[i] = T2; H2->TheTrees[i] = NULL; break;
		case 4: /* 100 */  H1->TheTrees[i] = Carry; Carry = NULL; break;
		case 3: /* 011 */  Carry = CombineTrees( T1, T2 );
			            H1->TheTrees[i] = H2->TheTrees[i] = NULL; break;
		case 5: /* 101 */  Carry = CombineTrees( T1, Carry );
			            H1->TheTrees[i] = NULL; break;
		case 6: /* 110 */  Carry = CombineTrees( T2, Carry );
			            H2->TheTrees[i] = NULL; break;
		case 7: /* 111 */  H1->TheTrees[i] = Carry; 
			            Carry = CombineTrees( T1, T2 ); 
			            H2->TheTrees[i] = NULL; break;
	    } /* end switch */
	} /* end for-loop */
	return H1;
}

• 4*!!Carry + 2*!!T2 + !!T1的作用是将树转换为二进制表示，对于第一个非，如果是空，那么为1，如果非空，那么为0，再取非，就再取反，然后转换为3位的二进制数字
• 000什么都不用做，此时三个位置都是0
• 001什么都不用做，此时H1有树，H2没有东西需要合并上去的
• 010此时将H2的树转移到H1
• 011需要进位，Carry要变成两树之和，两树要清空
• 100将Carry转移到H1
• 101需要进位,当位置0，将Carry变得更大
• 110与上一情况类似
• 111这里的做法并不唯一，我们可以保留任意一棵树,将另外两树之和进位上去，不过这里采用的是保留Carry,进位T1+T2

Deletemin

ElementType  DeleteMin( BinQueue H )
{	BinQueue DeletedQueue; 
	Position DeletedTree, OldRoot;
	ElementType MinItem = Infinity;  /* the minimum item to be returned */	
	int i, j, MinTree; /* MinTree is the index of the tree with the minimum item */

	if ( IsEmpty( H ) )  {  PrintErrorMessage();  return –Infinity; }

	for ( i = 0; i < MaxTrees; i++) {  /* Step 1: find the minimum item */
	    if( H->TheTrees[i] && H->TheTrees[i]->Element < MinItem ) { 
		MinItem = H->TheTrees[i]->Element;  MinTree = i;    } /* end if */
	} /* end for-i-loop */

	DeletedTree = H->TheTrees[ MinTree ];  
	H->TheTrees[ MinTree ] = NULL;   /* Step 2: remove the MinTree from H => H’ */ 
	OldRoot = DeletedTree;   /* Step 3.1: remove the root */ 
	DeletedTree = DeletedTree->LeftChild;   free(OldRoot);
	DeletedQueue = Initialize();   /* Step 3.2: create H” */ 

	DeletedQueue->CurrentSize = ( 1<<MinTree ) – 1;  /* 2^{MinTree} – 1 */
	
    for ( j = MinTree – 1; j >= 0; j – – ) {  
	    DeletedQueue->TheTrees[j] = DeletedTree;
	    DeletedTree = DeletedTree->NextSibling;
	    DeletedQueue->TheTrees[j]->NextSibling = NULL;
	} //将树拆开
	
    H->CurrentSize  – = DeletedQueue->CurrentSize + 1;//minus 2^{MinTree}
    H = Merge( H, DeletedQueue ); /* Step 4: merge H’ and H” */ 
	return MinItem;
}

ElementType DeleteMin(BinQueue H)

BinQueue DeletedQueue; 
Position DeletedTree, OldRoot;
ElementType MinItem = Infinity; 
int i, j, MinTree;

if (IsEmpty(H)) { PrintErrorMessage(); return -Infinity; }

for (i = 0; i < MaxTrees; i++) {
    if (H->TheTrees[i] && H->TheTrees[i]->Element < MinItem) { 
        MinItem = H->TheTrees[i]->Element;  
        MinTree = i;    
    }
}

DeletedTree = H->TheTrees[MinTree];  
H->TheTrees[MinTree] = NULL;   
OldRoot = DeletedTree;   
DeletedTree = DeletedTree->LeftChild;   
free(OldRoot);

DeletedQueue = Initialize();   
DeletedQueue->CurrentSize = (1 << MinTree) - 1;  

for (j = MinTree - 1; j >= 0; j--) {  
    DeletedQueue->TheTrees[j] = DeletedTree;
    DeletedTree = DeletedTree->NextSibling;
    DeletedQueue->TheTrees[j]->NextSibling = NULL;
}

H->CurrentSize -= DeletedQueue->CurrentSize + 1; 
H = Merge(H, DeletedQueue);

return MinItem;

堆性能的总结(单步摊还代价)