二项堆是Vuillemin发明，这种数据结构，能够有效支持插入，删除 混合 检索最小 等操作，优点是结构比较精致，而且比较简单。
闲言少叙，上代码。
#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;
}
