Construct Binomial Heap

// Include header file
#include <stdio.h>
#include <stdlib.h>

/*
    C program 
    Construct Binomial Heap
*/
// Define TreeNode
struct TreeNode
{
    int key;
    int child_count;
    struct TreeNode *sibling;
    struct TreeNode *parent;
    struct TreeNode *child;
};
// Define BinomialHeap
struct BinomialHeap
{
    struct TreeNode *root;
};
// Returns a new node of tree
struct TreeNode *newNode(int key, struct TreeNode *sibling)
{
    struct TreeNode *node = (struct TreeNode *) malloc(sizeof(struct TreeNode));
    if (node != NULL)
    {
        node->key = key;
        node->sibling = sibling;
        // Set default value of node
        node->child = NULL;
        node->parent = NULL;
        node->child_count = 0;
    }
    else
    {
        printf("\n Memory Overflow to create tree node\n");
    }
    return node;
}
// This is provide new Binomial Heap Tree
struct BinomialHeap *newTree()
{
    struct BinomialHeap *tree = (struct BinomialHeap *) malloc(sizeof(struct BinomialHeap));
    if (tree != NULL)
    {
        tree->root = NULL;
    }
    else
    {
        printf("\n Memory Overflow to create new tree \n");
    }
    return tree;
}
// Determine that whether the given node and next sibling tree have same number of children nodes
int isCombine(struct TreeNode *node)
{
    if (node != NULL && node->sibling != NULL 
        && node->child_count == node->sibling->child_count)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
// This is attack child tree into parent tree
struct TreeNode *changeRelation(struct TreeNode *parentNode, struct TreeNode *childNode)
{
    if (parentNode->sibling == childNode)
    {
        parentNode->sibling = childNode->sibling;
    }
    childNode->sibling = parentNode->child;
    parentNode->child = childNode;
    childNode->parent = parentNode;
    parentNode->child_count += 1;
    return parentNode;
}
// Recursively merging of two tree
struct TreeNode *merge(struct TreeNode *node1, struct TreeNode *node2)
{
    struct TreeNode *temp = NULL;
    if (node1->key < node2->key)
    {
        temp = changeRelation(node1, node2);
    }
    else
    {
        temp = changeRelation(node2, node1);
    }
    if (isCombine(temp) == 1)
    {
        temp = merge(temp, temp->sibling);
    }
    return temp;
}
// Handles the request of add new key into the tree
void insert(struct BinomialHeap *tree, int key)
{
    // Create new node of tree
    struct TreeNode *node = newNode(key, tree->root);
    if (tree->root == NULL)
    {
        // When add subtree node
        tree->root = node;
    }
    else if (isCombine(node) == 1)
    {
        // When need to combine two sibling 
        tree->root = merge(node, tree->root);
    }
    else
    {
        tree->root = node;
    }
}

// In-order view of Binomial Heap from left to right in top tree
void print_tree(struct TreeNode *node)
{
    if (node == NULL)
    {
        return;
    }
    printf("  %d", node->key);
    // Visit of child and sibling nodes
    print_tree(node->child);
    print_tree(node->sibling);
}
// Return minimum key value of tree
int minimum(struct TreeNode *root)
{
    if (root == NULL)
    {
        // When empty tree
        return -1;
    }
    struct TreeNode *auxiliary = root;
    int result = root->key;
    // Find last node
    while (auxiliary != NULL)
    {
        if (result > auxiliary->key)
        {
            result = auxiliary->key;
        }
        auxiliary = auxiliary->sibling;
    }
    return result;
}

int main()
{
    struct BinomialHeap *tree = newTree();
    // Add tree element
    insert(tree, 6);
    insert(tree, 5);
    insert(tree, 9);
    insert(tree, 3);
    insert(tree, 4);
    insert(tree, 11);
    insert(tree, 1);
    insert(tree, 7);
    insert(tree, 12);
    insert(tree, 10);
    insert(tree, 21);
    insert(tree, 14);
    insert(tree, 6);
    printf("\n Constructing Binomial Heap \n");
    /*
    Constructing of Binomial Heap
    ==========================
    6-------10 ------------- 1
           / |            /  | \   
         14  |           /   |  \
         |   12         3    4   7
         21            / \   |
                      /   \  |
                      5    9 11
                      |
                      |
                      6
    ==========================
    Logical view    
    */
    print_tree(tree->root);
    printf("\n Minimum node : %d ", minimum(tree->root));
    return 0;
}

Output

 Constructing Binomial Heap
  6  10  14  21  12  1  3  5  6  9  4  11  7
 Minimum node : 1