数据结构与算法分析（三）——二项队列

引论

左堆的合并，插入，删除最小的时间复杂度为O(logN)。二项队列就是为了对这些结果进一步提高的一种数据结构。利用二项队列，这三种操作的最坏时间复杂度为O(logN)，但是插入的平均时间复杂度为O(1)

二项队列

二项队列不是一棵树，它是一个森林，由一组堆序的树组成的深林，叫做二项队列。

二项队列有几个性质比较重要

（a）每一颗树都是一个有约束的堆序树，叫做二项树

（b）高度为k的第k个二项树Bk由一个根节点和B0, B1, .......B(k-1)构成

（c）高度为k的二项树的结点个数为2^k

我们可以用二项树的结合表示任意大小的优先队列。例如，大小为13的优先队列就可以用B3，B2，B0来表示，二进制的表示为1101。对此，我深表怀疑二项队列是不是受二进制的启发而产生的。

数据结构与算法分析（三）——二项队列

二项队列的操作

查找最小项：只需要查找每个二项树的根节点就可以了，因此时间复杂度为O(logN)。

合并：通过把两个队列相加在一起完成。因为有O(logN)棵树，所以合并的时间复杂度也是O(logN)。

插入：插入也是一种合并，只不过是把插入的结点当做B0。虽然感觉插入的时间复杂度是O(logN)，但是实际是O(1)，因为有一定的概率是被插入的二项队列没有B0。

删除最小：在根结点找到最小值，然后把最小值所在的树单独拿出分列为二项队列，然后把这个新的二项队列与原二项队列进行合并。每一个过程的时间复杂度为O(logN)。故加起来的时间复杂度仍为O(logN)。

这些操作归根结底是合并Merge。

数据结构与算法分析（三）——二项队列

二项队列的代码实现

(1) 二项队列声明：

 1 typedef struct BinNode *Position; 
 2 typedef struct BinNode *BinTree; 
 3 typedef struct Collection *BinQueue; 
 4 struct BinNode 
 5 { 
 6  ElementType Element; 
 7  Position LeftChild; 
 8  Position Sibling; 
 9 }; 
10 struct Collection 
11 { 
12     int CurrentSize; 
13  BinTree TheTrees[MaxTree]; 
14 } 
15

首先定义了树BinNode，然后定义了森林Collection。

下图是TheTrees，数组里装的是指向个个二项树的指针。以及二项队列在上面定义的结构里面的表示方式。可以看出，根节点仅指向一个有最多子树的子结点，由这个结点指向各个兄弟节点，所以访问必然是逐级访问。

数据结构与算法分析（三）——二项队列

(2)合并树：

合并树本质是指针的变动。当然要对两个二项树做好变换。

1  
2 BinTree CombineTree(BinTree T1,BinTree T2) 
3 { 
4     if(T1->Element>T2->Element) 
5         return CombineTree(T2,T1); 
6     T2->Sibling = T1->LeftChild; 
7     T1->LeftChild = T2; 
8     return T1; 
9 }

数据结构与算法分析（三）——二项队列

(3)合并两个优先队列（merge）：

 1 BinQueue Merge(BinQueue H1, BinQueue H2)  
 2 {  
 3     BinTree T1, T2, Carry = NULL;  
 4     int i,j;  
 5     if(H1->CurrentSize+H2->CurrentSize>Capacity)  
 6         Error("Exceed the Capacity");  
 7     H1->CurrentSize = H1->CurrentSize + H2->CurrentSize;  //CurrentSize含义：
 8     for(i=0,j=1;j<H1->CurrentSize;i++,j*=2)  //j：用于中止循环条件
 9     {  
10         T1 = H1->TheTrees[i];  
11         T2 = H2->TheTrees[i];  
12         switch(!!T1+2*!!T2+4*!!Carry)  
13         {  
14             case 0: //No Trees  
15             case 1: //Only H1  
16                 break;   
17             case 2:   
18                 H1->TheTrees[i] = T2;  
19                 H2->TheTrees[i] = NULL;  
20                 break;  
21             case 4: //Only Carry  
22                 H1->TheTrees[i] = Carry;  
23                 Carry = NULL;  
24                 break;  
25             case 3: //T1,T2  
26                 Carry = CombineTree(T1,T2);  
27                 H1->TheTrees[i] = H2->TheTrees[i] = NULL;  
28                 break;  
29             case 5:  
30                 Carry = CombineTree(T1,Carry);  
31                 H1->TheTrees[i] = NULL;  
32                 break;  
33             case 6:  
34                 Carry = CombineTree(T2,Carry);  
35                 H2->TheTrees[i] = NULL;  
36                 break;  
37             case 7:  
38                 H1->TheTrees[i] = Carry;  
39                 Carry = CombineTree(T1,T2);  
40                 H2->TheTrees[i] = NULL;  
41                 break;  
42         }  
43     }  
44     return H1;  
45 }

在这段程序中，switch语句的加法是很不错的。

还有一个问题就是：怎么控制需要几阶二项队列，这直接导致程序要循环几次的问题。这里把两个二项队列的大小相加，假设是12的话，那么应该是4阶，因为3阶的大小为1+2+4 = 9<12，故应该为四阶，这也是循环控制的方式。

1 for(i=0,j=1;j<H1->CurrentSize;i++,j*=2)

(4)删除最小值（DeleteMin）：

 1 ElementType DeleteMin(BinQueue H)  
 2 {  
 3     int i,j;  
 4     int MinTree;  
 5     BinQueue DeleteQueue;  
 6     Position DeletedTree, OldRoot;  
 7     ElementType MinItem;  
 8   
 9     if(IsEmpty(H))  
10     {  
11         Error("Empty BinQueue!!");  
12         return -Infinity;  
13     }  
14     //find the minmum  
15     Min = Infinity;  
16     for(i=0;i<MaxTree;i++)  
17     {  
18         if(H->TheTrees[i] && H->TheTrees[i]->Element<MinItem)  
19         {  
20             // Updata the minmun  
21             MiniItem = H->TheTrees[i]->Element;  
22             MinTree = i;  
23         }  
24     }  
25     // have found the DeleteTree  
26     DeleteTree = H->TheTrees[MinTree];  
27     OldRoot = DeleteTree;  
28     DeleteTree = OldRoot->LeftChild;  
29     free(OldRoot);  
30   
31     // form the DeleteQueue  
32     DeletedQueue = Initialize();  
33     DeletedQueue->CurrentSize = (1<<MinTree) - 1;  //左移Mintree位
34   
35     for(j=MinTree-1;j>=0;j--)  
36     {  
37         DeletedQueue->TheTree[j] = DeletedTree;  
38         DeletedTree = DeletedTree->Sibling;  
39         DeletedQueue->TheTree[j]->Sibling = NULL;  
40     }  
41     H->TheTrees[MiniTree] = NULL;  
42     H->CurrentSize -= DeletedQueue->CurrentSize+1;  
43   
44     Merge(H,DeletedQueue);  
45     return MinItem;  
46   
47 }

转自：http://blog.csdn.net/changyuanchn/article/details/14648463

秒客网

数据结构与算法分析（三）——二项队列

相关文章