【转】二项队列分析及实现

只看该作者 · 2017-1-5 12:30

定义：

二项队列不同于左式堆和二叉堆等优先队列的实现之处在于，一个二项队列不是一棵堆序的树，而是堆序树的集合，即森林。堆序树中的每棵树都是由约束形式的，叫做二项树。每一个高度上至多存在一棵二项树。高度为0的二项树是一颗单节点树，高度为k的二项树Bk通过将一棵二项树Bk-1附接到另一颗二项树Bk-1的根上而构成。下图显示二项树B0，B1，B2，B3以及B4。

二项队列的复杂度
左堆的合并，插入，删除最小的时间复杂度为O(logN)。二项队列就是为了对这些结果进一步提高的一种数据结构。利用二项队列，这三种操作的最坏时间复杂度为O(logN)，但是插入的平均时间复杂度为O(1)。
基本操作：
合并：
二项队列的合并操作可以看做一个简单的二进制加法运算，从低位运算到高位。首先是两个队列的B0相加，如果两个队列都存在B0（二进制为1），因此将两个B0合并成一个B1树，生成的B1树当做进位，参与下一步的B1运算，直到运算到最高位结束。

删除最小值/最大值：
删除最小值首先要做的事情就是找到最小值。那么只要寻找二项队列对应的每一刻Bk树的根节点中的最小值即可。然后把拥有最小值的Bk树删去根节点。此时剩下的树为B0，B1...Bk-1树。这些树构成一个新的二项队列，然后调用上述的合并操作，既可以完成删除操作。
插入：
插入操作等同于合并操作，非常好完成。
编码实现：
二项队列定义：
在对二项队列编码之前，需要明白如何表示二项队列。因为二项队列的根节点所指向的节点可能是无限的，所以不能像二叉树那样使用两个指针来指向两个儿子（这里有无数个儿子）。
具体的表示方式如下图所示：
第一张图代表我们画出来的二项队列。
第二张图上半部分的数组是指向树节点的指针，即指向Bk的根节点。
每个树节点有三个元素，Element，Leftchild， NextSibling。
其中NextSibling指的是和它本身同级的兄弟。如第一张图中的B3，
12没有同级兄弟，21,24,23互为同级兄弟，65,51,24互为同级兄弟。
那么Leftchild元素指向谁呢，当然是指向有最多孩子的节点，提取出来就是B2的23节点了。
理解了这里，在看第二张图想必会明白多了。
合并：

合并操作的主要内容就是做二进制加法运算，使用switch来进行判断。具体到两个Bk树的合并非常的简单，如下图所示：

然较小的根节点变成新的根，另一个Bk成为它的左孩子，它原来的左孩子成为另一个Bk根节点的兄弟。

详细代码：

头文件：

[cpp] view plain copy

typedef long ElementType;
#define Infinity (30000L)
#ifndef _BinHeap_H
#define _BinHeap_H
#define MaxTrees (14) //二项队列中的二项树高度最大为13；
#define Capacity (16383) //高度0,1,2,3，...，13的二项树节点数目之和
struct BinNode; //二项树节点
typedef struct BinNode *BinTree; //二项树
struct Collection;
typedef struct Collection *BinQueue;
BinQueue Initialize(void);
void Destroy( BinQueue H);
BinQueue MakeEmpty(BinQueue H);
BinQueue Insert(ElementType Item, BinQueue H);
ElementType DeleteMin(BinQueue H);
BinTree CombineTrees( BinTree T1, BinTree T2 ); //合并两棵相同大小的树
BinQueue Merge(BinQueue H1, BinQueue H2);
ElementType FindMin(BinQueue H);
int IsEmpty(BinQueue H);
int IsFull(BinQueue H);
#endif

只看该作者 · 2017-1-5 12:31

源文件：

[cpp] view plain copy

#include "binomial.h"
#include <stdio.h>
#include <stdlib.h>
typedef struct BinNode *Position;
struct BinNode
{
ElementType Element;
Position LeftChild;
Position NextSibling;
};
struct Collection
{
int CurrentSize;
BinTree TheTrees[MaxTrees]; //数组，该数组每个元素都是一棵二项树
};
BinQueue Initialize()
{
BinQueue H;
int i = 0;
H = malloc(sizeof(struct Collection));
if (H == NULL){
printf("Out of space!!\n");
return NULL;
}
H->CurrentSize = 0; //设置二项队列初始大小为0，每棵二项树均为NULL
for (i = 0; i < MaxTrees; ++i){
H->TheTrees = NULL;
}
return H;
}
static void DestroyTree(BinTree T)
{
//递归删除二项树的所有节点
if (T != NULL){
DestroyTree(T->LeftChild);
DestroyTree(T->NextSibling);
free(T);
}
}
void Destroy(BinQueue H)
{
//释放二项队列所占空间：通过删除所有的二项树完成
int i = 0;
for (i = 0; i < MaxTrees; ++i){
DestroyTree(H->TheTrees);
}
}
BinQueue MakeEmpty(BinQueue H)
{
int i = 0;
Destroy(H); //首先释放H所占空间
for (i = 0; i < MaxTrees; ++i){
H->TheTrees = NULL;
}
H->CurrentSize = 0; //二项队列当前大小
return H;
}
BinQueue Insert(ElementType Item, BinQueue H)
{
BinTree NewNode; //二项树B0
BinQueue OneItem; //只有B0的二项队列
NewNode = malloc(sizeof(struct BinNode));
if (NewNode == NULL){
printf("Out of space!\n");
return H;
}
NewNode->Element = Item;
NewNode->LeftChild = NewNode->NextSibling = NULL;
OneItem = Initialize();
OneItem->CurrentSize = 1;
OneItem->TheTrees[0] = NewNode;
return Merge(H, OneItem); //合并单节点的二项树构成的二项队列与H
}
ElementType FindMin(BinQueue H)
{
int i = 0;
ElementType MinItem;
if (IsEmpty(H)){
printf("Empty binomial queue");
return -1;
}
MinItem = Infinity;
//遍历二项队列中的所有二项树，比较它们的根
for (i = 0; i < MaxTrees; ++i){
if (H->TheTrees && H->TheTrees->Element < MinItem){
MinItem = H->TheTrees->Element;
}
}
return MinItem;
}
int IsEmpty(BinQueue H)
{
return H->CurrentSize == 0; //currentsize存放二项队列中节点的个数
}
int IsFull(BinQueue H)
{
return H->CurrentSize == Capacity;
}
BinTree CombineTrees( BinTree T1, BinTree T2 )
{
//合并相同大小的两颗二项树
if (T1 == NULL)
return T2;
else if (T2 == NULL)
return T1;
if (T1->Element > T2->Element)
return CombineTrees(T2, T1);
//根大的树做为根小的树的左儿子
T2->NextSibling = T1->LeftChild;
T1->LeftChild = T2;
return T1;
}
BinQueue Merge(BinQueue H1, BinQueue H2)
{
BinTree T1, T2, Carry = NULL;
int i = 0, j = 0;
//首先判断合并是否会超出二项队列限制的大小
if (H1->CurrentSize + H2->CurrentSize > Capacity){
printf("Merge would exceed capacity!\n");
return H1;
}
H1->CurrentSize += H2->CurrentSize;
//遍历H1，H2中所有的二项树
for (i = 0, j = 1; j <= H1->CurrentSize; ++i, j *= 2){
T1 = H1->TheTrees;
T2 = H2->TheTrees;
//若T1为空，!!T1则为0，否则为1
switch(!!T1 + 2* (!!T2) + 4 * (!!Carry)){
case 0:
case 1:
break;
case 2:
//只有T2存在，直接将T2放入二项队列H1中对应的位置；
H1->TheTrees = T2;
H2->TheTrees = NULL;
break;
case 3:
//T1与T2均存在，合并相同大小的二项树
Carry = CombineTrees(T1, T2);
H1->TheTrees = NULL;
H2->TheTrees = NULL;
break;
case 4:
//由上一步合并而得的二项树作为二项队列H1的一部分
H1->TheTrees = Carry;
Carry = NULL;
break;
case 5:
Carry = CombineTrees(T1, Carry);
H1->TheTrees = NULL;
break;
case 6:
Carry = CombineTrees(T2, Carry);
H2->TheTrees = NULL;
break;
case 7:
H1->TheTrees = Carry;
Carry = CombineTrees(T1, T2);
H2->TheTrees = NULL;
break;
}
}
return H1;
}
ElementType DeleteMin(BinQueue H)
{
int i = 0, j = 0;
int MinTree; //用来存放根最小的二项树的高度
BinQueue DeletedQueue;
Position DeletedTree, OldRoot;
ElementType MinItem;
if (IsEmpty(H)){
printf("Empty binomial queue!\n");
return -1;
}
MinItem = Infinity;
//遍历二项队列，找出根元素最小的二项树
for (i = 0; i < MaxTrees; ++i){
if (H->TheTrees && H->TheTrees->Element < MinItem){
MinItem = H->TheTrees->Element;
MinTree = i;
}
}
DeletedTree = H->TheTrees[MinTree];
OldRoot = DeletedTree;
DeletedTree = DeletedTree->LeftChild;
free(OldRoot); //删除根元素；
DeletedQueue = Initialize();
//将1左移MinTree位，即得到高度为MinTree的二项树的大小
//因为高度为k的二项树的大小是2^k,减1是因为删除了根
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->TheTrees[MinTree] = NULL;
H->CurrentSize -= DeletedQueue->CurrentSize + 1; //新二项队列的大小；
Merge(H, DeletedQueue);
return MinItem;
}

【转】二项队列分析及实现

相关帖子