首页 > 代码库 > 二项队列
二项队列
二项队列是 堆序 的集合，也叫 森林。其中每一种形式都有约束。
二项树Bk由一个带有儿子的B0,B1,B2...组成，高度为k的二项树 恰好有2^k个结点。每一种高度只能出现一次...因此，只有1,2,4,8...等结点数目的二项树
deleteMin操作需要快速的找出跟的所有子树的能力，因此需要一般树的表示方法：
每个结点的儿子都在一个链表中，而且每个结点都有一个指向它的第一个儿子的指针。
二项树的每一个结点包括：数据，第一个儿子，以及右兄弟
下面是二项队列类构架及结点定义：
1 template <typename Comparable>
2 class BinomialQueue
3 {
4 public:
5 BinomialQueue();
6 BinomialQueue(const Comparable & item);
7 BinomialQueue(const BinomialQueue & rhs);
8 ~BinomialQueue();
9
10 bool isEmpty() const;
11 const Comparable & findMin() const;
12
13 void insert(const Comparable & x);
14 void deleteMin();
15 void deleteMin(Comparable & minItem);
16
17 void makeEmpty();
18 void merge(BinomialQueue & rhs);
19
20 const BinomialQueue & operator=(const BinomialQueue & rhs);
21 private:
22 struct BinomialNode
23 {
24 Comparable element;
25 BinomiaNode *leftChild;
26 BinomialNode *nextSibling;
27
28 BinomialNode(const Comparable & theElement,BinomialNode *lt,BinomialNode *rt)
29 :element(theElement),leftChild(lt),rightChild(rt)
30 {
31 }
32 };
33
34 enum{DEFAULT_TREES = 1};
35
36 int currentSize;
37 vector<BinomialNode *> const;
38 int capacity() const;
39 BinomialNode * combineTrees(BinomialNode *t1,BinomialNode *t2);
40 void makeEmpty(BinomialNode * & t);
41 BinomialNode * clone(BinomialNode *t) const;
42 };
合并同样大小的两棵树二项树的例程：
1 BinomialNode * combineTrees(BinomialNode *t1,BinomialNode *t2)
2 {
3 if(t2->element < t1->element)
4 return combineTrees(t2,t1);
5 t1->nextSibling = t1->leftChild;
6 t1->leftChild = t2;
7 return t1;
8 }
合并两个优先队列的例程：
1 void merge(BinomialQueue & rhs)
2 {
3 if(this==&rhs)
4 return;
5 currentSize += rhs.currentSize;
6 if(currentSize > capacity())
7 {
8 int oldNumTrees = theTrees.size();
9 int newNumTrees = max(theTrees.size(),rhs.theTrees.size())+1;
10 theTrees.resize(newNumTrees);
11 for(int i = oldNumTrees; i<newNumTrees; i++)
12 theTrees[i] = NULL;
13 }
14 BinomialNode *carry = NULL;
15 for(int i=0,j=1; j<=currentSize; i++,j*=2)
16 {
17 BinomialNode *t1 = theTrees[i];
18 BinomialNode *t2 = i < rhs.theTrees.size()? rhs.theTrees[i]:NULL;
19
20 int whichCase = t1 == NULL ? 0 : 1;
21 whichCase += t2 == NULL? 0 : 2;
22 whichCase += carry == NULL? 0 : 4;
23
24 switch(whichCase)
25 {
26 case 0:
27 case 1:
28 break;
29 case 2:
30 theTrees[i] = t2;
31 rhs.theTrees[i] = NULL;
32 break;
33 case 4:
34 theTrees[i] = carry;
35 carry = NULL;
36 break;
37 case 3:
38 carry = combineTrees(t1,t2);
39 theTrees[i] = rhs.theTrees[i] = NULL;
40 break;
41 case 5:
42 carry = combineTrees(t1,carry);
43 theTrees[i] = NULL;
44 break;
45 case 6:
46 carry = combineTrees(t2,carry);
47 rhs.theTrees[i] = NULL;
48 break;
49 case 7:
50 theTrees[i] = carry;
51 carry = combineTrees(t1,t2);
52 rhs.theTrees[i] = NULL;
53 break;
54 }
55 }
56 for(int k = 0; k < rhs.theTrees.size(); k++)
57 rhs.theTrees[k] = NULL;
58 rhs.currentSize = 0;
59 }
deleteMin程序：
1 void deleteMin(Comparable & minItem)
2 {
3 if(isEmpty())
4 throw UnderflowException();
5 int minIndex = findMinIndex();
6 minItem = theTrees[minIndex]->element;
7
8 BinomialNode *oldRoot = theTrees[minIndex];
9 BinomialNode *deletedTree = oldRoot->leftChild;
10 delete oldRoot;
11
12 BinomialQueue deletedQueue;
13 deletedQueue.theTrees.resize(minIndex+1);
14 deletedQueue.currentSize = (1<<minIndex)-1;
15 for(int j = minIndex -1 ;j >= 0 ; j--)
16 {
17 deletedQueue.theTrees[ j ] = deletedTree;
18 deletedTree = deletedTree->nextSibling;
19 deletedQueue.theTrees[ j ]->nextSibling = NULL;
20 }
21
22 theTrees[minIndex] = NULL;
23 currentSize -= deletedQueue.currentSize + 1;
24
25 merge(deletedQueue);
26 }
27 int findMinIndex() const
28 {
29 int i;
30 int minIndex;
31
32 for( i = 0; theTrees[i] === NULL;i++)
33 ;
34 for(minIndex = i; i < theTrees.size();i++)
35 if(theTrees[i] != NULL && theTrees[i]->element < theTrees[minIndex]->element)
36 minIndex = i;
37
38 return minIndex;
39 }
二项队列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。