Binomial Heap in C++

This C++ Program demonstrates the implementation of Binomial Heap.

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

```
/*
```

 * C++ Program to Implement Binomial Heap

```
 */
```
```
#include <iostream>
```
```
#include <cstdlib>
```
```
using namespace std;
```
```
/*
```
```
 * Node Declaration
```
```
 */
```
```
struct node
```
```
{
```
```
    int n;
```
```
    int degree;
```
```
    node* parent;
```
```
    node* child;
```
```
    node* sibling;
```
```
};
```
```
/*
```
```
 * Class Declaration
```
```
 */
```
```
class BinomialHeap
```
```
{
```
```
    private:
```
```
        node *H;
```
```
        node *Hr;
```
```
        int count;
```
```
    public:
```
```
        node* Initializeheap();
```

        int Binomial_link(node*, node*);

```
        node* Create_node(int);
```
```
        node* Union(node*, node*);
```
```
        node* Insert(node*, node*);
```
```
        node* Merge(node*, node*);
```
```
        node* Extract_Min(node*);
```
```
        int Revert_list(node*);
```
```
        int Display(node*);
```
```
        node* Search(node*, int);
```

        int Decrease_key(node*, int, int);

```
        int Delete(node*, int);
```
```
        BinomialHeap()
```
```
        {
```
```
            H = Initializeheap();
```
```
            Hr = Initializeheap();
```
```
            int count = 1;
```
```
        }
```
```
};
```
```
 
```
```
/*
```
```
 * Initialize Heap
```
```
 */
```
```
node* BinomialHeap::Initializeheap()
```
```
{
```
```
    node* np;
```
```
    np = NULL;
```
```
    return np;
```
```
}
```
```
/*
```
```
 * Linking nodes in Binomial Heap
```
```
 */
```

int BinomialHeap::Binomial_link(node* y, node* z)

```
{
```
```
    y->parent = z;
```
```
    y->sibling = z->child;
```
```
    z->child = y;
```
```
    z->degree = z->degree + 1;
```
```
}
```
```
/*
```
```
 * Create Nodes in Binomial Heap
```
```
 */
```
```
node* BinomialHeap::Create_node(int k)
```
```
{
```
```
    node* p = new node;
```
```
    p->n = k;
```
```
    return p;
```
```
}
```
```
/*
```
```
 * Insert Nodes in Binomial Heap
```
```
 */
```

node* BinomialHeap::Insert(node* H, node* x)

```
{
```
```
    node* H1 = Initializeheap();
```
```
    x->parent = NULL;
```
```
    x->child = NULL;
```
```
    x->sibling = NULL;
```
```
    x->degree = 0;
```
```
    H1 = x;
```
```
    H = Union(H, H1);
```
```
    return H;
```
```
}
```
```
 
```
```
/*
```
```
 * Union Nodes in Binomial Heap
```
```
 */
```

node* BinomialHeap::Union(node* H1, node* H2)

```
{
```
```
    node *H = Initializeheap();
```
```
    H = Merge(H1, H2);
```
```
    if (H == NULL)
```
```
        return H;
```
```
    node* prev_x;
```
```
    node* next_x;
```
```
    node* x;
```
```
    prev_x = NULL;
```
```
    x = H;
```
```
    next_x = x->sibling;
```
```
    while (next_x != NULL)
```
```
    {
```

        if ((x->degree != next_x->degree) || ((next_x->sibling != NULL)

            && (next_x->sibling)->degree == x->degree))

```
        {
```
```
            prev_x = x;
```
```
            x = next_x;
```
```
        }
```
```
        else
```
```
	    {
```
```
            if (x->n <= next_x->n)
```
```
            {
```

                x->sibling = next_x->sibling;

                Binomial_link(next_x, x);

```
            }
```
```
            else
```
```
            {
```
```
                if (prev_x == NULL)
```
```
                    H = next_x;
```
```
                else
```

                    prev_x->sibling = next_x;

                Binomial_link(x, next_x);

```
                x = next_x;
```
```
            }
```
```
	    }
```
```
        next_x = x->sibling;
```
```
    }
```
```
    return H;
```
```
}
```
```
/*
```
```
 * Merge Nodes in Binomial Heap
```
```
 */
```

node* BinomialHeap::Merge(node* H1, node* H2)

```
{
```
```
    node* H = Initializeheap();
```
```
    node* y;
```
```
    node* z;
```
```
    node* a;
```
```
    node* b;
```
```
    y = H1;
```
```
    z = H2;
```
```
    if (y != NULL)
```
```
    {
```
```
        if (z != NULL)
```
```
        {
```
```
            if (y->degree <= z->degree)
```
```
                H = y;
```

            else if (y->degree > z->degree)

```
                H = z;
```
```
        }
```
```
        else
```
```
            H = y;
```
```
    }
```
```
    else
```
```
        H = z;
```
```
    while (y != NULL && z != NULL)
```
```
    {
```
```
        if (y->degree < z->degree)
```
```
        {
```
```
            y = y->sibling;
```
```
        }
```

        else if (y->degree == z->degree)

```
        {
```
```
            a = y->sibling;
```
```
            y->sibling = z;
```
```
            y = a;
```
```
        }
```
```
        else
```
```
        {
```
```
            b = z->sibling;
```
```
            z->sibling = y;
```
```
            z = b;
```
```
        }
```
```
    }
```
```
    return H;
```
```
}
```
```
/*
```
```
 * Display Binomial Heap
```
```
 */
```
```
int BinomialHeap::Display(node* H)
```
```
{
```
```
    if (H == NULL)
```
```
    {
```

        cout<<"The Heap is empty"<<endl;

```
        return 0;
```
```
    }
```
```
    cout<<"The root nodes are: "<<endl;
```
```
    node* p;
```
```
    p = H;
```
```
    while (p != NULL)
```
```
    {
```
```
        cout<<p->n;
```
```
        if (p->sibling != NULL)
```
```
            cout<<"-->";
```
```
        p = p->sibling;
```
```
    }
```
```
    cout<<endl;
```
```
}
```
```
/*
```
```
 * Extract Minimum
```
```
 */
```

node* BinomialHeap::Extract_Min(node* H1)

```
{
```
```
    Hr = NULL;
```
```
    node* t = NULL;
```
```
    node* x = H1;
```
```
    if (x == NULL)
```
```
    {
```

        cout<<"Nothing to Extract"<<endl;

```
        return x;
```
```
    }
```
```
    int min = x->n;
```
```
    node* p = x;
```
```
    while (p->sibling != NULL)
```
```
    {
```
```
        if ((p->sibling)->n < min)
```
```
        {
```
```
            min = (p->sibling)->n;
```
```
            t = p;
```
```
            x = p->sibling;
```
```
        }
```
```
        p = p->sibling;
```
```
    }
```

    if (t == NULL && x->sibling == NULL)

```
        H1 = NULL;
```
```
    else if (t == NULL)
```
```
        H1 = x->sibling;
```
```
    else if (t->sibling == NULL)
```
```
        t = NULL;
```
```
    else
```
```
        t->sibling = x->sibling;
```
```
    if (x->child != NULL)
```
```
    {
```
```
        Revert_list(x->child);
```
```
        (x->child)->sibling = NULL;
```
```
    }
```
```
    H = Union(H1, Hr);
```
```
    return x;
```
```
}
```
```
/*
```
```
 * Reverse List
```
```
 */
```
```
int BinomialHeap::Revert_list(node* y)
```
```
{
```
```
    if (y->sibling != NULL)
```
```
    {
```
```
        Revert_list(y->sibling);
```
```
        (y->sibling)->sibling = y;
```
```
    }
```
```
    else
```
```
    {
```
```
        Hr = y;
```
```
    }
```
```
}
```
```
 
```
```
/*
```
```
 * Search Nodes in Binomial Heap
```
```
 */
```

node* BinomialHeap::Search(node* H, int k)

```
{
```
```
    node* x = H;
```
```
    node* p = NULL;
```
```
    if (x->n == k)
```
```
    {
```
```
        p = x;
```
```
        return p;
```
```
    }
```
```
    if (x->child != NULL && p == NULL)
```
```
        p = Search(x->child, k);
```

    if (x->sibling != NULL && p == NULL)

```
        p = Search(x->sibling, k);
```
```
    return p;
```
```
}
```
```
/*
```
```
 * Decrease key of a node
```
```
 */
```

int BinomialHeap::Decrease_key(node* H, int i, int k)

```
{
```
```
    int temp;
```
```
    node* p;
```
```
    node* y;
```
```
    node* z;
```
```
    p = Search(H, i);
```
```
    if (p == NULL)
```
```
    {
```

        cout<<"Invalid choice of key"<<endl;

```
        return 0;
```
```
    }
```
```
    if (k > p->n)
```
```
    {
```

        cout<<"Error!! New key is greater than current key"<<endl;

```
        return 0;
```
```
    }
```
```
    p->n = k;
```
```
    y = p;
```
```
    z = p->parent;
```
```
    while (z != NULL && y->n < z->n)
```
```
    {
```
```
        temp = y->n;
```
```
        y->n = z->n;
```
```
        z->n = temp;
```
```
        y = z;
```
```
        z = z->parent;
```
```
    }
```

    cout<<"Key reduced successfully"<<endl;

```
}
```
```
/*
```
```
 * Delete Nodes in Binomial Heap
```
```
 */
```

int BinomialHeap::Delete(node* H, int k)

```
{
```
```
    node* np;
```
```
    if (H == NULL)
```
```
    {
```
```
        cout<<"\nHEAP EMPTY!!!!!";
```
```
        return 0;
```
```
    }
```
```
    Decrease_key(H, k, -1000);
```
```
    np = Extract_Min(H);
```
```
    if (np != NULL)
```

        cout<<"Node Deleted Successfully"<<endl;

```
}
```
```
/*
```
```
 * Main Contains Menu
```
```
 */
```
```
int main()
```
```
{
```
```
    int n, m, l, i;
```
```
    BinomialHeap bh;
```
```
    node* p;
```
```
    node *H;
```
```
    H = bh.Initializeheap();
```
```
    char ch;
```
```
    while (1)
```
```
    {
```

        cout<<"----------------------------"<<endl;

        cout<<"Operations on Binomial heap"<<endl;

        cout<<"----------------------------"<<endl;

        cout<<"1)Insert Element in the heap"<<endl;

        cout<<"2)Extract Minimum key node"<<endl;

        cout<<"3)Decrease key of a node"<<endl;

```
        cout<<"4)Delete a node"<<endl;
```
```
        cout<<"5)Display Heap"<<endl;
```
```
        cout<<"6)Exit"<<endl;
```
```
        cout<<"Enter Your Choice: ";
```
```
        cin>>l;
```
```
        switch(l)
```
```
        {
```
```
        case 1:
```

            cout<<"Enter the element to be inserted: ";

```
            cin>>m;
```
```
            p = bh.Create_node(m);
```
```
            H = bh.Insert(H, p);
```
```
            break;
```
```
        case 2:
```
```
            p = bh.Extract_Min(H);
```
```
            if (p != NULL)
```

                cout<<"The node with minimum key: "<<p->n<<endl;

```
            else
```

                cout<<"Heap is empty"<<endl;

```
            break;
```
```
        case 3:
```

            cout<<"Enter the key to be decreased: ";

```
            cin>>m;
```

            cout<<"Enter new key value: ";

```
            cin>>l;
```
```
            bh.Decrease_key(H, m, l);
```
```
            break;
```
```
        case 4:
```

            cout<<"Enter the key to be deleted: ";

```
            cin>>m;
```
```
            bh.Delete(H, m);
```
```
            break;
```
```
        case 5:
```

            cout<<"The Heap is: "<<endl;

```
            bh.Display(H);
```
```
            break;
```
```
        case 6:
```
```
            exit(1);
```
```
        default:
```
```
            cout<<"Wrong Choice";
```
```
	  }
```
```
    }
```
```
    return 0;
```
```
}
```

$ g++ binomialheap.cpp
$ a.out
----------------------------
Operations on Binomial heap
----------------------------
1)Insert Element in the heap
2)Extract Minimum key node
3)Decrease key of a node
4)Delete a node
5)Display Heap
6)Exit
Enter Your Choice: 1
Enter the element to be inserted: 9
----------------------------
Operations on Binomial heap
----------------------------
1)Insert Element in the heap
2)Extract Minimum key node
3)Decrease key of a node
4)Delete a node
5)Display Heap
6)Exit
Enter Your Choice: 1
Enter the element to be inserted: 8
----------------------------
Operations on Binomial heap
----------------------------
1)Insert Element in the heap
2)Extract Minimum key node
3)Decrease key of a node
4)Delete a node
5)Display Heap
6)Exit
Enter Your Choice: 1
Enter the element to be inserted: 7
----------------------------
Operations on Binomial heap
----------------------------
1)Insert Element in the heap
2)Extract Minimum key node
3)Decrease key of a node
4)Delete a node
5)Display Heap
6)Exit
Enter Your Choice: 1
Enter the element to be inserted: 6
----------------------------
Operations on Binomial heap
----------------------------
1)Insert Element in the heap
2)Extract Minimum key node
3)Decrease key of a node
4)Delete a node
5)Display Heap
6)Exit
Enter Your Choice: 1
Enter the element to be inserted: 5
----------------------------
Operations on Binomial heap
----------------------------
1)Insert Element in the heap
2)Extract Minimum key node
3)Decrease key of a node
4)Delete a node
5)Display Heap
6)Exit
Enter Your Choice: 2
The node with minimum key: 5
----------------------------
Operations on Binomial heap
----------------------------
1)Insert Element in the heap
2)Extract Minimum key node
3)Decrease key of a node
4)Delete a node
5)Display Heap
6)Exit
Enter Your Choice: 4
Enter the key to be deleted: 6
Key reduced successfully
Node Deleted Successfully
----------------------------
Operations on Binomial heap
----------------------------
1)Insert Element in the heap
2)Extract Minimum key node
3)Decrease key of a node
4)Delete a node
5)Display Heap
6)Exit
Enter Your Choice: 2
The node with minimum key: 5
----------------------------
Operations on Binomial heap
----------------------------
1)Insert Element in the heap
2)Extract Minimum key node
3)Decrease key of a node
4)Delete a node
5)Display Heap
6)Exit
Enter Your Choice: 5
The root nodes are: 
5
----------------------------
Operations on Binomial heap
----------------------------
1)Insert Element in the heap
2)Extract Minimum key node
3)Decrease key of a node
4)Delete a node
5)Display Heap
6)Exit
Enter Your Choice: 6
 
 
------------------
(program exited with code: 1)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

If you wish to look at all C++ Programming examples, go to C++ Programs.

If you find any mistake above, kindly email to [email protected]

« Prev - C++ Program to Implement Heap

» Next - C++ Program to Implement Binary Heap

Related Posts:

Practice Design & Analysis of Algorithms MCQ
Check Computer Science Books
Practice Programming MCQs
Check Data Structure Books
Practice Computer Science MCQs

Recommended Articles: