Chinaunix首页 | 论坛 | 博客
  • 博客访问: 3664498
  • 博文数量: 146
  • 博客积分: 3918
  • 博客等级: 少校
  • 技术积分: 8581
  • 用 户 组: 普通用户
  • 注册时间: 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-03-13 09:10:42

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


  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<assert.h>

  4. #define MIN_KEY 0xFFFFFFFF
  5. typedef struct __Bino_node{
  6.     int key;
  7.     int value;
  8.     int degree;
  9.     struct __Bino_node *parent;
  10.     struct __Bino_node *child;
  11.     struct __Bino_node *next;
  12. } Bino_node;

  13. typedef struct{
  14.     Bino_node *head;
  15. }Bino_heap;

  16. int CreatBinomialHeap(Bino_heap *heap)
  17. {
  18.     (heap)->head = NULL;
  19.     return 0;
  20. }

  21. int BinomialLink(Bino_node *root,Bino_node *y)
  22. {
  23.     y->parent = root;
  24.     y->next = root->child;
  25.     root->child = y;
  26.     root->degree++;

  27.     return 0;
  28. }

  29. int InitBinomialNode(Bino_node* node ,int key ,int value)
  30. {
  31.     if(node == NULL)
  32.     {
  33.         return -1;
  34.     }

  35.     node->key = key;
  36.     node->value = value;
  37.     node->degree = 0;
  38.     node->parent = NULL;
  39.     node->child = NULL;
  40.     node->next = NULL;
  41.     return 0;
  42. }

  43. Bino_node* BinomialHeapMerge(Bino_node* a,Bino_node* b)
  44. {
  45.     Bino_node *head = NULL;
  46.     Bino_node **pos = &head;

  47.     while(a && b)
  48.     {
  49.         if(a->degree < b->degree)
  50.         {
  51.             *pos = a;
  52.             a = a->next;
  53.         }
  54.         else
  55.         {
  56.             *pos = b;
  57.             b = b->next;
  58.         }
  59.         pos = &(*pos)->next;

  60.     }

  61.     if(a)
  62.         *pos = a;
  63.     else
  64.         *pos = b;
  65.     return head;

  66. }
  67. int BinomialHeapUnion(Bino_heap* heapx,Bino_heap* heapy)
  68. {
  69.     Bino_node *head = NULL;
  70.     Bino_node *prev ,*cur,*next;
  71.     if(heapx == NULL || heapy == NULL)
  72.     {
  73.         printf("at least one heap point is null\r\n");
  74.         return -1;
  75.     }

  76.     head = BinomialHeapMerge(heapx->head,heapy->head);
  77.     prev = NULL;
  78.     cur = head;
  79.     next = head->next;
  80.     while(next)
  81.     {
  82.         if(cur->degree != next->degree ||
  83.                 (next->next)&&(next->degree == next->next->degree))
  84.         {
  85.             prev = cur;
  86.             cur = next;
  87.             next = cur->next;
  88.         }
  89.         else
  90.         {
  91.             if(cur->key <next->key)
  92.             {
  93.                 cur->next = next->next;
  94.                 BinomialLink(cur,next);
  95.                 next = cur->next;
  96.             }
  97.             else
  98.             {
  99.                 if(prev == NULL)
  100.                     head = next;
  101.                 else
  102.                     prev->next = next;
  103.                 BinomialLink(next,cur);
  104.                 cur = next;
  105.                 next = cur->next;
  106.             }
  107.         }
  108.     }

  109.     heapx->head = head;
  110.     return 0;
  111. }


  112. int BinomialHeapInsertNode(Bino_heap* heap,Bino_node* node)
  113. {
  114.     Bino_heap heap2 = {0};
  115.     int ret = -1;
  116.     if(heap ==NULL || node == NULL)
  117.     {
  118.         printf("heap or node is null pointer\r\n");
  119.         return -1;
  120.     }

  121.     ret = CreatBinomialHeap(&heap2);
  122.     if(ret)
  123.     {
  124.         printf("create new heap failed \r\n");
  125.         return -2;
  126.     }

  127.     heap2.head = node;

  128.     BinomialHeapUnion(heap,&heap2);
  129.     return 0;
  130. }

  131. Bino_node* BinomialReverse(Bino_node *node)
  132. {
  133.     Bino_node* tail = NULL;
  134.     Bino_node* next;

  135.     if(node == NULL)
  136.     {
  137.         return node;
  138.     }

  139.     node->parent = NULL;
  140.     while(node->next)
  141.     {
  142.         next = node->next;
  143.         node->next = tail;
  144.         tail = node;
  145.         node = next;
  146.         node->parent = NULL;
  147.     }

  148.     node->next = tail;
  149.     return node;

  150. }

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

  157.     while(cur->next)
  158.     {
  159.         if((*min_node)->key > cur->next->key)
  160.         {
  161.             *min_node = cur->next;
  162.             prev = cur;

  163.         }
  164.         cur = cur->next;
  165.     }

  166.     if(prev == NULL)
  167.         heap->head = (*min_node)->next;
  168.     else
  169.         prev->next = (*min_node)->next;

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

  174. int BinomialHeapDecreaseKey(Bino_heap* heap,Bino_node *node,int newkey)
  175. {
  176.     Bino_node *parent = NULL;
  177.     int tmp_key;
  178.     int tmp_value;
  179.     if(newkey > node->key)
  180.     {
  181.         printf("new key is big than old key,should exit\r\n");
  182.         return -1;
  183.     }

  184.     node->key = newkey;
  185.     parent = node->parent;

  186.     while(parent && parent->key > node->key)
  187.     {
  188.         tmp_key = parent->key;
  189.         tmp_value = parent->value;
  190.         parent->key = node->key;
  191.         parent->value = node->value;
  192.         node->key = tmp_key;
  193.         node->value = tmp_value;

  194.         node = parent;
  195.         parent = node->parent;
  196.     }
  197.     return 0;

  198. }

  199. int BinomialHeapDelete(Bino_heap* heap,Bino_node *node)
  200. {
  201.     Bino_node *min_node = NULL;
  202.     BinomialHeapDecreaseKey(heap,node,MIN_KEY);
  203.     ExtractBinomialHeapMin(heap,&min_node);
  204.     return 0;
  205. }

  206. void test_del()
  207. {

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

  210.     CreatBinomialHeap(&heap);

  211.     InitBinomialNode(&node1,3,55);
  212.     BinomialHeapInsertNode(&heap,&node1);

  213.     InitBinomialNode(&node2,11,43);
  214.     BinomialHeapInsertNode(&heap,&node2);

  215.     InitBinomialNode(&node3,9,65);
  216.     BinomialHeapInsertNode(&heap,&node3);

  217.     InitBinomialNode(&node4,7,78);
  218.     BinomialHeapInsertNode(&heap,&node4);

  219.     InitBinomialNode(&node5,15,44);
  220.     BinomialHeapInsertNode(&heap,&node5);

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

  225. }
  226. void test_BinomialHeapDecreaseKey()
  227. {

  228. }
  229. void test_ExtractBinomialHeapMin()
  230. {

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

  233.     CreatBinomialHeap(&heap);

  234.     InitBinomialNode(&node1,rand(),rand());
  235.     BinomialHeapInsertNode(&heap,&node1);

  236.     InitBinomialNode(&node2,rand(),rand());
  237.     BinomialHeapInsertNode(&heap,&node2);

  238.     InitBinomialNode(&node3,rand(),rand());
  239.     BinomialHeapInsertNode(&heap,&node3);

  240.     InitBinomialNode(&node4,rand(),rand());
  241.     BinomialHeapInsertNode(&heap,&node4);

  242.     InitBinomialNode(&node5,rand(),rand());
  243.     BinomialHeapInsertNode(&heap,&node5);

  244.     InitBinomialNode(&node6,17,78);
  245.     BinomialHeapInsertNode(&heap,&node6);

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

  249. }
  250. void test_BinomialHeapInsertNode()
  251. {
  252.     Bino_heap heap = {0};
  253.     Bino_node node1,node2,node3,node4,node5,node6;

  254.     CreatBinomialHeap(&heap);

  255.     InitBinomialNode(&node1,3,55);
  256.     BinomialHeapInsertNode(&heap,&node1);

  257.     InitBinomialNode(&node2,11,43);
  258.     BinomialHeapInsertNode(&heap,&node2);

  259.     InitBinomialNode(&node3,9,65);
  260.     BinomialHeapInsertNode(&heap,&node3);

  261.     InitBinomialNode(&node4,7,78);
  262.     BinomialHeapInsertNode(&heap,&node4);

  263.     InitBinomialNode(&node5,15,44);
  264.     BinomialHeapInsertNode(&heap,&node5);

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


  267. }
  268. void test_BinomialHeapMerge()
  269. {
  270.     Bino_node a ={0};
  271.     Bino_node b = {0};
  272.     Bino_node *head = NULL;
  273.     InitBinomialNode(&a,6 ,66);
  274.     InitBinomialNode(&b,7,777);
  275.     head = BinomialHeapMerge(&a,&b);
  276.     printf("head->key:%d\thead->value :%d\r\n",head->key,head->value);
  277.     printf("head->next->key :%d\thead->next->value :%d\r\n",head->next->key,head->next->value);

  278. }
  279. void test_FineBinomialHeapMin()
  280. {

  281. }
  282. void test_CreatBinomialHeap()
  283. {
  284.     Bino_heap heap = {0};
  285.     int ret;
  286.     ret =    CreatBinomialHeap(&heap);
  287.     if(ret == 0)
  288.     {
  289.         printf("the address of heap is %ld \r\n",(long)heap.head);
  290.     }

  291. }
  292. void test_Bino_heap()
  293. {
  294.     Bino_heap heap;
  295. }
  296. void test_Bino_node()
  297. {
  298.     Bino_node node;
  299. }
  300. int test()
  301. {
  302.     //test_Bino_node();
  303.     //test_Bino_heap();
  304.     //test_CreatBinomialHeap();
  305.     //test_BinomialHeapMerge();
  306.     //test_BinomialHeapInsertNode();
  307.     //test_BinomialReverse();
  308.     //test_ExtractBinomialHeapMin();
  309.     test_del();

  310. }
  311. int main()
  312. {
  313.     test();
  314.     return 0;
  315. }

阅读(2052) | 评论(1) | 转发(0) |
给主人留下些什么吧!~~

chinaunix网友2011-03-27 18:42:34

很好的, 收藏了 推荐一个博客,提供很多免费软件编程电子书下载: http://free-ebooks.appspot.com