C Program to Implement Binomial Heap

«
»
This is a C Program to implement Binomial heap. Binomial heap is a heap, just like binary heap, additional feature that it supports quick merging of two heaps.

Here is source code of the C Program to Implement Binomial Heap. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /* C program to implement Binomial Heap tree */
  2.  
  3. #include<stdio.h>
  4. #include<malloc.h>
  5.  
  6. struct node {
  7.     int n;
  8.     int degree;
  9.     struct node* parent;
  10.     struct node* child;
  11.     struct node* sibling;
  12. };
  13.  
  14. struct node* MAKE_bin_HEAP();
  15. int bin_LINK(struct node*, struct node*);
  16. struct node* CREATE_NODE(int);
  17. struct node* bin_HEAP_UNION(struct node*, struct node*);
  18. struct node* bin_HEAP_INSERT(struct node*, struct node*);
  19. struct node* bin_HEAP_MERGE(struct node*, struct node*);
  20. struct node* bin_HEAP_EXTRACT_MIN(struct node*);
  21. int REVERT_LIST(struct node*);
  22. int DISPLAY(struct node*);
  23. struct node* FIND_NODE(struct node*, int);
  24. int bin_HEAP_DECREASE_KEY(struct node*, int, int);
  25. int bin_HEAP_DELETE(struct node*, int);
  26.  
  27. int count = 1;
  28.  
  29. struct node* MAKE_bin_HEAP() {
  30.     struct node* np;
  31.     np = NULL;
  32.     return np;
  33. }
  34.  
  35. struct node * H = NULL;
  36. struct node *Hr = NULL;
  37.  
  38. int bin_LINK(struct node* y, struct node* z) {
  39.     y->parent = z;
  40.     y->sibling = z->child;
  41.     z->child = y;
  42.     z->degree = z->degree + 1;
  43. }
  44.  
  45. struct node* CREATE_NODE(int k) {
  46.     struct node* p;//new node;
  47.     p = (struct node*) malloc(sizeof(struct node));
  48.     p->n = k;
  49.     return p;
  50. }
  51.  
  52. struct node* bin_HEAP_UNION(struct node* H1, struct node* H2) {
  53.     struct node* prev_x;
  54.     struct node* next_x;
  55.     struct node* x;
  56.     struct node* H = MAKE_bin_HEAP();
  57.     H = bin_HEAP_MERGE(H1, H2);
  58.     if (H == NULL)
  59.         return H;
  60.     prev_x = NULL;
  61.     x = H;
  62.     next_x = x->sibling;
  63.     while (next_x != NULL) {
  64.         if ((x->degree != next_x->degree) || ((next_x->sibling != NULL)
  65.                 && (next_x->sibling)->degree == x->degree)) {
  66.             prev_x = x;
  67.             x = next_x;
  68.         } else {
  69.             if (x->n <= next_x->n) {
  70.                 x->sibling = next_x->sibling;
  71.                 bin_LINK(next_x, x);
  72.             } else {
  73.                 if (prev_x == NULL)
  74.                     H = next_x;
  75.                 else
  76.                     prev_x->sibling = next_x;
  77.                 bin_LINK(x, next_x);
  78.                 x = next_x;
  79.             }
  80.         }
  81.         next_x = x->sibling;
  82.     }
  83.     return H;
  84. }
  85.  
  86. struct node* bin_HEAP_INSERT(struct node* H, struct node* x) {
  87.     struct node* H1 = MAKE_bin_HEAP();
  88.     x->parent = NULL;
  89.     x->child = NULL;
  90.     x->sibling = NULL;
  91.     x->degree = 0;
  92.     H1 = x;
  93.     H = bin_HEAP_UNION(H, H1);
  94.     return H;
  95. }
  96.  
  97. struct node* bin_HEAP_MERGE(struct node* H1, struct node* H2) {
  98.     struct node* H = MAKE_bin_HEAP();
  99.     struct node* y;
  100.     struct node* z;
  101.     struct node* a;
  102.     struct node* b;
  103.     y = H1;
  104.     z = H2;
  105.     if (y != NULL) {
  106.         if (z != NULL && y->degree <= z->degree)
  107.             H = y;
  108.         else if (z != NULL && y->degree > z->degree)
  109.             /* need some modifications here;the first and the else conditions can be merged together!!!! */
  110.             H = z;
  111.         else
  112.             H = y;
  113.     } else
  114.         H = z;
  115.     while (y != NULL && z != NULL) {
  116.         if (y->degree < z->degree) {
  117.             y = y->sibling;
  118.         } else if (y->degree == z->degree) {
  119.             a = y->sibling;
  120.             y->sibling = z;
  121.             y = a;
  122.         } else {
  123.             b = z->sibling;
  124.             z->sibling = y;
  125.             z = b;
  126.         }
  127.     }
  128.     return H;
  129. }
  130.  
  131. int DISPLAY(struct node* H) {
  132.     struct node* p;
  133.     if (H == NULL) {
  134.         printf("\nHEAP EMPTY");
  135.         return 0;
  136.     }
  137.     printf("\nTHE ROOT NODES ARE:-\n");
  138.     p = H;
  139.     while (p != NULL) {
  140.         printf("%d", p->n);
  141.         if (p->sibling != NULL)
  142.             printf("-->");
  143.         p = p->sibling;
  144.     }
  145.     printf("\n");
  146. }
  147.  
  148. struct node* bin_HEAP_EXTRACT_MIN(struct node* H1) {
  149.     int min;
  150.     struct node* t = NULL;
  151.     struct node* x = H1;
  152.     struct node *Hr;
  153.     struct node* p;
  154.     Hr = NULL;
  155.     if (x == NULL) {
  156.         printf("\nNOTHING TO EXTRACT");
  157.         return x;
  158.     }
  159.     //    int min=x->n;
  160.     p = x;
  161.     while (p->sibling != NULL) {
  162.         if ((p->sibling)->n < min) {
  163.             min = (p->sibling)->n;
  164.             t = p;
  165.             x = p->sibling;
  166.         }
  167.         p = p->sibling;
  168.     }
  169.     if (t == NULL && x->sibling == NULL)
  170.         H1 = NULL;
  171.     else if (t == NULL)
  172.         H1 = x->sibling;
  173.     else if (t->sibling == NULL)
  174.         t = NULL;
  175.     else
  176.         t->sibling = x->sibling;
  177.     if (x->child != NULL) {
  178.         REVERT_LIST(x->child);
  179.         (x->child)->sibling = NULL;
  180.     }
  181.     H = bin_HEAP_UNION(H1, Hr);
  182.     return x;
  183. }
  184.  
  185. int REVERT_LIST(struct node* y) {
  186.     if (y->sibling != NULL) {
  187.         REVERT_LIST(y->sibling);
  188.         (y->sibling)->sibling = y;
  189.     } else {
  190.         Hr = y;
  191.     }
  192. }
  193.  
  194. struct node* FIND_NODE(struct node* H, int k) {
  195.     struct node* x = H;
  196.     struct node* p = NULL;
  197.     if (x->n == k) {
  198.         p = x;
  199.         return p;
  200.     }
  201.     if (x->child != NULL && p == NULL) {
  202.         p = FIND_NODE(x->child, k);
  203.     }
  204.  
  205.     if (x->sibling != NULL && p == NULL) {
  206.         p = FIND_NODE(x->sibling, k);
  207.     }
  208.     return p;
  209. }
  210.  
  211. int bin_HEAP_DECREASE_KEY(struct node* H, int i, int k) {
  212.     int temp;
  213.     struct node* p;
  214.     struct node* y;
  215.     struct node* z;
  216.     p = FIND_NODE(H, i);
  217.     if (p == NULL) {
  218.         printf("\nINVALID CHOICE OF KEY TO BE REDUCED");
  219.         return 0;
  220.     }
  221.     if (k > p->n) {
  222.         printf("\nSORY!THE NEW KEY IS GREATER THAN CURRENT ONE");
  223.         return 0;
  224.     }
  225.     p->n = k;
  226.     y = p;
  227.     z = p->parent;
  228.     while (z != NULL && y->n < z->n) {
  229.         temp = y->n;
  230.         y->n = z->n;
  231.         z->n = temp;
  232.         y = z;
  233.         z = z->parent;
  234.     }
  235.     printf("\nKEY REDUCED SUCCESSFULLY!");
  236. }
  237.  
  238. int bin_HEAP_DELETE(struct node* H, int k) {
  239.     struct node* np;
  240.     if (H == NULL) {
  241.         printf("\nHEAP EMPTY");
  242.         return 0;
  243.     }
  244.  
  245.     bin_HEAP_DECREASE_KEY(H, k, -1000);
  246.     np = bin_HEAP_EXTRACT_MIN(H);
  247.     if (np != NULL)
  248.         printf("\nNODE DELETED SUCCESSFULLY");
  249. }
  250.  
  251. int main() {
  252.     int i, n, m, l;
  253.     struct node* p;
  254.     struct node* np;
  255.     char ch;
  256.     printf("\nENTER THE NUMBER OF ELEMENTS:");
  257.     scanf("%d", &n);
  258.     printf("\nENTER THE ELEMENTS:\n");
  259.     for (i = 1; i <= n; i++) {
  260.         scanf("%d", &m);
  261.         np = CREATE_NODE(m);
  262.         H = bin_HEAP_INSERT(H, np);
  263.     }
  264.     DISPLAY(H);
  265.     do {
  266.         printf("\nMENU:-\n");
  267.         printf(
  268.                 "\n1)INSERT AN ELEMENT\n2)EXTRACT THE MINIMUM KEY NODE\n3)DECREASE A NODE KEY\n 4)DELETE A NODE\n5)QUIT\n");
  269.         scanf("%d", &l);
  270.         switch (l) {
  271.         case 1:
  272.             do {
  273.                 printf("\nENTER THE ELEMENT TO BE INSERTED:");
  274.                 scanf("%d", &m);
  275.                 p = CREATE_NODE(m);
  276.                 H = bin_HEAP_INSERT(H, p);
  277.                 printf("\nNOW THE HEAP IS:\n");
  278.                 DISPLAY(H);
  279.                 printf("\nINSERT MORE(y/Y)= \n");
  280.                 fflush(stdin);
  281.                 scanf("%c", &ch);
  282.             } while (ch == 'Y' || ch == 'y');
  283.             break;
  284.         case 2:
  285.             do {
  286.                 printf("\nEXTRACTING THE MINIMUM KEY NODE");
  287.                 p = bin_HEAP_EXTRACT_MIN(H);
  288.                 if (p != NULL)
  289.                     printf("\nTHE EXTRACTED NODE IS %d", p->n);
  290.                 printf("\nNOW THE HEAP IS:\n");
  291.                 DISPLAY(H);
  292.                 printf("\nEXTRACT MORE(y/Y)\n");
  293.                 fflush(stdin);
  294.                 scanf("%c", &ch);
  295.             } while (ch == 'Y' || ch == 'y');
  296.             break;
  297.         case 3:
  298.             do {
  299.                 printf("\nENTER THE KEY OF THE NODE TO BE DECREASED:");
  300.                 scanf("%d", &m);
  301.                 printf("\nENTER THE NEW KEY : ");
  302.                 scanf("%d", &l);
  303.                 bin_HEAP_DECREASE_KEY(H, m, l);
  304.                 printf("\nNOW THE HEAP IS:\n");
  305.                 DISPLAY(H);
  306.                 printf("\nDECREASE MORE(y/Y)\n");
  307.                 fflush(stdin);
  308.                 scanf("%c", &ch);
  309.             } while (ch == 'Y' || ch == 'y');
  310.             break;
  311.         case 4:
  312.             do {
  313.                 printf("\nENTER THE KEY TO BE DELETED: ");
  314.                 scanf("%d", &m);
  315.                 bin_HEAP_DELETE(H, m);
  316.                 printf("\nDELETE MORE(y/Y)\n");
  317.                 fflush(stdin);
  318.                 scanf("%c", &ch);
  319.             } while (ch == 'y' || ch == 'Y');
  320.             break;
  321.         case 5:
  322.             printf("\nTHANK U SIR\n");
  323.             break;
  324.         default:
  325.             printf("\nINVALID ENTRY...TRY AGAIN....\n");
  326.         }
  327.     } while (l != 5);
  328. }

Output:

advertisement
$ gcc BinomialHeap.c
$ ./a.out
 
ENTER THE NUMBER OF ELEMENTS:5
ENTER THE ELEMENTS:12 23 34 45 56
 
THE ROOT NODES ARE:-
56-->12
 
MENU:-
 
1)INSERT AN ELEMENT
2)EXTRACT THE MINIMUM KEY NODE
3)DECREASE A NODE KEY
 4)DELETE A NODE
5)QUIT
1
ENTER THE ELEMENT TO BE INSERTED:67
NOW THE HEAP IS:
 
THE ROOT NODES ARE:-
56-->12
 
INSERT MORE(y/Y)= n
 
MENU:-
 
1)INSERT AN ELEMENT
2)EXTRACT THE MINIMUM KEY NODE
3)DECREASE A NODE KEY
 4)DELETE A NODE
5)QUIT
 
ENTER THE ELEMENT TO BE DELETED:67
NOW THE HEAP IS:
 
THE ROOT NODES ARE:-
67-->56-->12
 
DELETE MORE(y/Y)= n
 
MENU:-
 
1)INSERT AN ELEMENT
2)EXTRACT THE MINIMUM KEY NODE
3)DECREASE A NODE KEY
 4)DELETE A NODE
5)QUIT
 
THANK U SIR

Sanfoundry Global Education & Learning Series – 1000 C Programs.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement

Here’s the list of Best Books in C Programming, Data Structures and Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.