Fibonacci heap

// Fibonacci heap
// patata0717

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

// Node
typedef struct sNode {
    int key;    // value
    int degree; // number of child, LAZY(calculate while needed)
    bool mark;  // mark if has lost child
    struct sNode *leftSib;
    struct sNode *rightSib;
    struct sNode *parent;
    struct sNode *child;
} Node;

Node* _CreateNode(int key);
    // constructor

// FibonacciHeap
typedef struct sFibonacciHeap {
    int n;    // number of nodes
    Node *min;
    Node *rootList;
} FibonacciHeap;

FibonacciHeap* CreateFibonacciHeap();
    // constructor
Node* FindMin(FibonacciHeap* FH);
    // find mininum node
Node* Insert(FibonacciHeap* FH, int key);
    // insert new node
void _MergeWithDoublyList(FibonacciHeap* FH, Node** root, Node* node);
    // throw a node to a circular doubly linked list
FibonacciHeap* UnionFibonacciHeap(FibonacciHeap* FH1, FibonacciHeap* FH2);
    // union 2 heaps
Node* ExtractMin(FibonacciHeap* FH);
    // find min and remove min
void _RemoveFromRootList(FibonacciHeap* FH, Node* node);
    // remove a node on root list
void _Consolidate(FibonacciHeap* FH);
    // build binomial heap and set true min
void _HeapLink(FibonacciHeap* FH, Node* y, Node* x);
    // Make y child of x
void DecreaseKey(FibonacciHeap* FH, Node* x, int k);
    // Make a key smaller
void _Cut(FibonacciHeap* FH, Node* x, Node* y);
    // Throw a node from child to root list, reset mark
void _CascadingCut(FibonacciHeap* FH, Node* y);
    // Keep cutting until find a unmarked node
Node* Delete(FibonacciHeap* FH, Node* x);
    // Delete a node

int main(void)
{
    FibonacciHeap *FH1 = CreateFibonacciHeap();
    FibonacciHeap *FH2 = CreateFibonacciHeap();
    FibonacciHeap *FH3 = CreateFibonacciHeap();
    Node *N1;

    Insert(FH1, 1);
    Insert(FH1, 2);
    Insert(FH1, 3);
    Insert(FH2, 4);
    Insert(FH2, 5);
    Insert(FH2, 6);
    FH3 = UnionFibonacciHeap(FH1, FH2);
    N1 = ExtractMin(FH1);
    DecreaseKey(FH3, FH3->rootList, 1);
    Delete(FH3, FH3->rootList);

    return 0;
}

// Constructor
Node* _CreateNode(int key) {
    Node *node = (Node*)malloc(sizeof(Node));
    
    node->key = key;
    node->degree = 0;
    node->mark = false;
    node->leftSib = node;
    node->rightSib = node;
    node->parent = NULL;
    node->child = NULL;

    return node;
}

// Constructor
FibonacciHeap* CreateFibonacciHeap()
{
    FibonacciHeap *FH = (FibonacciHeap*)malloc(sizeof(FibonacciHeap));

    FH->n = 0;
    FH->min = NULL;
    FH->rootList = NULL;

    return FH;
}

// Find the minimum node
Node* FindMin(FibonacciHeap* FH)
{
    return FH->min;
}

// Insert new node
Node* Insert(FibonacciHeap* FH, int key)
{
    Node *node = _CreateNode(key);

    _MergeWithDoublyList(FH, &FH->rootList, node);

    if ((FH->min == NULL) || (node->key < FH->min->key))
        FH->min = node;

    FH->n++;

    return node;
}

// Throw a node to a circular doubly linked list
void _MergeWithDoublyList(FibonacciHeap* FH, Node** root, Node* node)
{
    if (*root == NULL) {
        *root = node;
    } else {
        // Insert node in the left next to the root
        // Adjusting circular doubly linked list for both node and root
        node->leftSib = *root;
        node->rightSib = (*root)->rightSib;
        (*root)->rightSib->leftSib = node;
        (*root)->rightSib = node;
    }
}

// Union 2 heaps
FibonacciHeap* UnionFibonacciHeap(FibonacciHeap* FH1, FibonacciHeap* FH2)
{
    FibonacciHeap *FH3 = CreateFibonacciHeap();

    // Use FH1's rootList
    FH3->rootList = FH1->rootList;

    // Insert FH2 in FH1 root's left
    FH2->rootList->rightSib->leftSib = FH3->rootList->leftSib;
    FH3->rootList->leftSib->rightSib = FH2->rootList->rightSib;
    FH2->rootList->rightSib = FH3->rootList;
    FH3->rootList->leftSib = FH2->rootList;

    // Choose the smaller min between FH1 and FH2
    if (FH1->min->key < FH2->min->key) {
        FH3->min = FH1->min;
    } else {
        FH3->min = FH2->min;
    }

    // Sum up numbers of node
    FH3->n = FH1->n + FH2->n;
    
    return FH3;
}

// Find min + Remove min
// Consolidate the heap
Node* ExtractMin(FibonacciHeap* FH)
{
    Node *node = FH->min;
    Node *temp;
    Node *next;
    Node *startPoint;

    if (node != NULL) {
        if (node->child != NULL) {
            // Throw all children to root list
            temp = node->child;
            startPoint = node->child;
            node->child = NULL;
            node->degree = 0;
            do {    
                next = temp->rightSib;
                temp->parent = NULL;
                temp->rightSib = temp;     
                temp->leftSib = temp;     
                _MergeWithDoublyList(FH, &FH->rootList, temp);
                    // throw it to root list
                temp = next;
            } while (temp != startPoint);   // while traversed end
        }

        // Remove min node
        _RemoveFromRootList(FH, node);
        FH->n--;

        // Do consolidate
        if (node->rightSib == node) {   // node is the only node on root list
            FH->min = NULL;             // (and it disappear now)
            FH->rootList = NULL;
        } else {
            FH->min = node->rightSib;   // assign min to its neighbor
            _Consolidate(FH);            // build binomial heap and set ture min
        }
    }
    return node;
}

// Remove node, noted that min is not corrent
void _RemoveFromRootList(FibonacciHeap* FH, Node* node)
{
    // Last node
    if (node->rightSib == node) {
        FH->rootList = NULL;
        FH->min = NULL;
    } else {
        // Accidentally delete root
        if (node == FH->rootList)
            FH->rootList = node->rightSib;  // root right shift

        // Accidentally delete min
        if (node == FH->min)
            FH->min = node->rightSib;
    
        // Remove node
        node->leftSib->rightSib = node->rightSib;
        node->rightSib->leftSib = node->leftSib;
    }
}

// Build binomial heap and set true min
void _Consolidate(FibonacciHeap* FH)
{
    Node **A;       // the A[] array
    Node *x, *y;    // new tree(iterate), original tree in A[d]
    Node *temp;     // swapping
    Node *x_copy;
    Node *next;
    Node *startingPoint;  
    int num;
    int i;
    int d;          // degree
    int size = 0;   // size of A

    // Calculate log2N(size of A)
    num = FH->n;
    while (num > 0) {
        num = num / 2;
        size++;
    }

    // Initialize A
    A = (Node**)malloc(size * sizeof(Node*));
    for (i = 0; i < size; i++) {
        A[i] = (Node*)malloc(sizeof(Node));
        A[i] = NULL;
    }

    // x traverse circular list a cycle
    x = FH->rootList;
    next = x->rightSib;
    while (x_copy != next) {
        x = next;
        x_copy = x;         // copy x for judging loop condition
        next = x->rightSib;
        d = x->degree;
        _RemoveFromRootList(FH, x);

        // Keep combining and incresing til find a vacant A[d]
        while (A[d] != NULL) {  // A[d] is occupied
            y = A[d];           // y get the original tree link

            // Combine trees,
            // larger root become subtree of smaller root
            if (x->key > y->key) {
                temp = x; x = y; y = temp;      // exchange x, y
            }
            _HeapLink(FH, y, x);                 // make y child of x
            A[d] = NULL;
            d++;            // increment degree 
        }
        A[d] = x;           // find a vacant A[d], x landed
    };
    
    // Add subtrees in A to root list
    for (i = 0; i < size; i++) {
        if (A[i] != NULL) {
            _MergeWithDoublyList(FH, &FH->rootList, A[i]);
                // throw A[i] to new root list
            
            // Find min
            if ((FH->min == NULL) || (A[i]->key < FH->min->key)) {
                FH->min = A[i];
            }
        }
    }
}

// Make y child of x
void _HeapLink(FibonacciHeap* FH, Node* y, Node* x)
{
    y->rightSib = y;
    y->leftSib = y;
    _MergeWithDoublyList(FH, &x->child, y);
        // merge y with x child's doubly list
    x->degree += 1;
    y->parent = x;
    y->mark = false;
}

void DecreaseKey(FibonacciHeap* FH, Node* x, int k) {
    Node *y;

    if (k > x->key) {
        return;
    }
    x->key = k;
    y = x->parent;
    if (y != NULL && x->key < y->key) {
        _Cut(FH, x, y);
        _CascadingCut(FH, y);
    }
    if (x->key < FH->min->key) {
        FH->min = x;
    }
}

// Throw a node from child to root list, reset mark
// y is parent, x is child
void _Cut(FibonacciHeap* FH, Node* x, Node* y) {
    // Remove child x from y
    y->child = NULL; 
    y->degree--;
    x->parent = NULL;
    x->rightSib = x;
    x->leftSib = x;
    _MergeWithDoublyList(FH, &FH->rootList, x);
    x->mark = false;
}

// Keep cutting until find a unmarked node
void _CascadingCut(FibonacciHeap* FH, Node* y) {
    Node *z = y->parent;

    if (z != NULL) {
        if (y->mark == false) {
            y->mark = true;
        } else {
            _Cut(FH, y, z);
            _CascadingCut(FH, z);
        }
    }
}

Node* Delete(FibonacciHeap* FH, Node* x)
{
    DecreaseKey(FH, x, -__INT_MAX__);
    return ExtractMin(FH);
}