Chinaunix首页 | 论坛 | 博客
  • 博客访问: 3883068
  • 博文数量: 146
  • 博客积分: 3918
  • 博客等级: 少校
  • 技术积分: 8585
  • 用 户 组: 普通用户
  • 注册时间: 2010-10-17 13:52
个人简介

个人微薄: weibo.com/manuscola

文章分类

全部博文(146)

文章存档

2016年(3)

2015年(2)

2014年(5)

2013年(42)

2012年(31)

2011年(58)

2010年(5)

分类: C/C++

2011-05-12 22:06:13

二项堆是Vuillemin发明,这种数据结构,能够有效支持插入,删除 混合 检索最小 等操作,优点是结构比较精致,而且比较简单。
闲言少叙,上代码。


#include
#include
#include

#define MIN_KEY 0xFFFFFFFF 
typedef struct __Bino_node{
int key;
int value;
int degree;
struct __Bino_node *parent;
struct __Bino_node *child;
struct __Bino_node *next;
} Bino_node;

typedef struct{
Bino_node *head;
}Bino_heap;

int CreatBinomialHeap(Bino_heap *heap)
{
(heap)->head = NULL;
return 0;
}

int BinomialLink(Bino_node *root,Bino_node *y)
{
y->parent = root;
y->next = root->child;
root->child = y;
root->degree ;

return 0;
}

int InitBinomialNode(Bino_node* node ,int key ,int value)
{
if(node == NULL)
{
return -1;
}

node->key = key;
node->value = value;
node->degree = 0;
node->parent = NULL;
node->child = NULL;
node->next = NULL;
return 0;
}

Bino_node* BinomialHeapMerge(Bino_node* a,Bino_node* b)
{
Bino_node *head = NULL;
Bino_node **pos = &head;

while(a && b)
{
if(a->degree < b->degree)
{
*pos = a;
a = a->next;
}
else
{
*pos = b;
b = b->next;
}
pos = &(*pos)->next;

}

if(a)
*pos = a;
else 
*pos = b;
return head;

}
int BinomialHeapUnion(Bino_heap* heapx,Bino_heap* heapy)
{
Bino_node *head = NULL;
Bino_node *prev ,*cur,*next;
if(heapx == NULL || heapy == NULL)
{
printf("at least one heap point is null\r\n");
return -1;
}

head = BinomialHeapMerge(heapx->head,heapy->head);
prev = NULL;
cur = head;
next = head->next;
while(next)
{
if(cur->degree != next->degree ||
(next->next)&&(next->degree == next->next->degree))
{
prev = cur;
cur = next;
next = cur->next;
}
else
{
if(cur->key key)
{
cur->next = next->next;
BinomialLink(cur,next);
next = cur->next;
}
else
{
if(prev == NULL)
head = next;
else
prev->next = next;
BinomialLink(next,cur);
cur = next;
next = cur->next;
}
}
}

heapx->head = head;
return 0;
}


int BinomialHeapInsertNode(Bino_heap* heap,Bino_node* node)
{
Bino_heap heap2 = {0};
int ret = -1;
if(heap ==NULL || node == NULL)
{
printf("heap or node is null pointer\r\n");
return -1;
}

ret = CreatBinomialHeap(&heap2);
if(ret)
{
printf("create new heap failed \r\n");
return -2;
}

heap2.head = node;

BinomialHeapUnion(heap,&heap2);
return 0;
}

Bino_node* BinomialReverse(Bino_node *node)
{
Bino_node* tail = NULL;
Bino_node* next;

if(node == NULL)
{
return node;
}

node->parent = NULL;
while(node->next)
{
next = node->next;
node->next = tail;
tail = node;
node = next;
node->parent = NULL; 
}

node->next = tail;
return node;

}

int ExtractBinomialHeapMin(Bino_heap *heap,Bino_node** min_node)
{
Bino_node* prev = NULL;  /*prev is to find the node previous of the min node*/
Bino_node* cur = heap->head;
*min_node = heap->head;
Bino_heap heap2;

while(cur->next)
{
if((*min_node)->key > cur->next->key)
{
*min_node = cur->next;
prev = cur;

}
cur = cur->next;
}

if(prev == NULL)
heap->head = (*min_node)->next;
else
prev->next = (*min_node)->next;

heap2.head = BinomialReverse((*min_node)->child);
BinomialHeapUnion(heap,&heap2);
return 0;
}

int BinomialHeapDecreaseKey(Bino_heap* heap,Bino_node *node,int newkey)
{
Bino_node *parent = NULL;
int tmp_key;
int tmp_value;
if(newkey > node->key)
{
printf("new key is big than old key,should exit\r\n");
return -1;
}

node->key = newkey;
parent = node->parent;

while(parent && parent->key > node->key)
{
tmp_key = parent->key;
tmp_value = parent->value;
parent->key = node->key;
parent->value = node->value;
node->key = tmp_key;
node->value = tmp_value;

node = parent;
parent = node->parent;
}
return 0;

}

int BinomialHeapDelete(Bino_heap* heap,Bino_node *node)
{
Bino_node *min_node = NULL;
BinomialHeapDecreaseKey(heap,node,MIN_KEY);
ExtractBinomialHeapMin(heap,&min_node);
return 0;
}

void test_del()
{

Bino_heap heap = {0};
Bino_node node1,node2,node3,node4,node5,node6;

CreatBinomialHeap(&heap);

InitBinomialNode(&node1,3,55);
BinomialHeapInsertNode(&heap,&node1);

InitBinomialNode(&node2,11,43);
BinomialHeapInsertNode(&heap,&node2);

InitBinomialNode(&node3,9,65);
BinomialHeapInsertNode(&heap,&node3);

InitBinomialNode(&node4,7,78);
BinomialHeapInsertNode(&heap,&node4);

InitBinomialNode(&node5,15,44);
BinomialHeapInsertNode(&heap,&node5);

BinomialHeapDelete(&heap,&node4);
assert(heap.head->key == 3);
assert(heap.head->child->next->key == 9);
assert(heap.head->child->child->key == 15);

}
void test_BinomialHeapDecreaseKey()
{

}
void test_ExtractBinomialHeapMin()
{

Bino_heap heap = {0};
Bino_node node1,node2,node3,node4,node5,node6;

CreatBinomialHeap(&heap);

InitBinomialNode(&node1,rand(),rand());
BinomialHeapInsertNode(&heap,&node1);

InitBinomialNode(&node2,rand(),rand());
BinomialHeapInsertNode(&heap,&node2);

InitBinomialNode(&node3,rand(),rand());
BinomialHeapInsertNode(&heap,&node3);

InitBinomialNode(&node4,rand(),rand());
BinomialHeapInsertNode(&heap,&node4);

InitBinomialNode(&node5,rand(),rand());
BinomialHeapInsertNode(&heap,&node5);

InitBinomialNode(&node6,17,78);
BinomialHeapInsertNode(&heap,&node6);

Bino_node *min_node;
ExtractBinomialHeapMin(&heap,&min_node);
printf("min_node Key is %d\r\n",min_node->key);

}
void test_BinomialHeapInsertNode()
{
Bino_heap heap = {0};
Bino_node node1,node2,node3,node4,node5,node6;

CreatBinomialHeap(&heap);

InitBinomialNode(&node1,3,55);
BinomialHeapInsertNode(&heap,&node1);

InitBinomialNode(&node2,11,43);
BinomialHeapInsertNode(&heap,&node2);

InitBinomialNode(&node3,9,65);
BinomialHeapInsertNode(&heap,&node3);

InitBinomialNode(&node4,7,78);
BinomialHeapInsertNode(&heap,&node4);

InitBinomialNode(&node5,15,44);
BinomialHeapInsertNode(&heap,&node5);

Bino_node* head = heap.head;
printf("head->key = %d,head->next->key : %d\r\n",head->key,head->next->key);


}
void test_BinomialHeapMerge()
{
Bino_node a ={0};
Bino_node b = {0};
Bino_node *head = NULL;
InitBinomialNode(&a,6 ,66);
InitBinomialNode(&b,7,777);
head = BinomialHeapMerge(&a,&b);
printf("head->key:%d\thead->value :%d\r\n",head->key,head->value);
printf("head->next->key :%d\thead->next->value :%d\r\n",head->next->key,head->next->value);

}
void test_FineBinomialHeapMin()
{

}
void test_CreatBinomialHeap()
{
Bino_heap heap = {0};
int ret;
ret = CreatBinomialHeap(&heap);
if(ret == 0)
{
printf("the address of heap is %ld \r\n",(long)heap.head);
}

}
void test_Bino_heap()
{
Bino_heap heap;
}
void test_Bino_node()
{
Bino_node node;
}
int test()
{
//test_Bino_node();
//test_Bino_heap();
//test_CreatBinomialHeap();
//test_BinomialHeapMerge();
//test_BinomialHeapInsertNode();
//test_BinomialReverse();
//test_ExtractBinomialHeapMin();
test_del();

}
int main()
{
test();
return 0;
}
阅读(1410) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~