fibo_heap.h

#pragma once
#include <string.h>
 
 
namespace cgv{
    namespace math{
 
template <typename key_type,typename value_type, int max_degrees=20>
class fibo_heap
{
    struct heap_node
    {
        heap_node* parent;
        heap_node* left;
        heap_node* right;
        heap_node* children[max_degrees];
        int num_children;
        int degree;
        key_type key;
        value_type value;
        
        heap_node(const key_type& _key, const value_type&_value)
        {
            left    = NULL;
            right   = NULL;
            parent  = NULL;
            key     = _key;
            value   =_value;
            degree  = 0;
            num_children   = 0;
            memset(children, 0, sizeof(children));
        }
 
        
    };
    public:
    fibo_heap()
    {
            root_heap = NULL;
            min_heap = NULL;
    }
 
    
 
    ~fibo_heap()
    {
        heap_node* node = root_heap;
            
        while (node != NULL)
        {
                    heap_node* next_node = node->right;
 
                    delete_tree(node);
                    node = next_node;
            }
 
    }
 
    void insert(const key_type& key, const value_type& value)
    {
        heap_node* new_node = new heap_node(key,value);
        add_to_root_heap(new_node);
 
    }
 
    value_type delete_min()
    {
         assert(min_heap != NULL);
 
         
         value_type k = min_heap->value;
         
         // Move the children into root
         level_up(min_heap);
 
         // Remove the minimum node
         remove_node(min_heap);
         min_heap = NULL;
 
         // Re-assign a new one for min_heap
         assign_min_node();
 
         // consolidate the heap trees
         consolidate();
        return k;
    }
 
    bool empty()
    {
        return min_heap == NULL;
    }
 
 
 
private:
    heap_node* root_heap;
    heap_node* min_heap;
 
 
    void add_to_root_heap(heap_node* node)
    {
        // First time
       if (root_heap == NULL)
            {
                    root_heap = node;
                    min_heap = node;
                    return;
            }
 
            // Add to the most left of the root heap
            node->right = root_heap;
            root_heap->left = node;
            root_heap = node;
 
            // Check the minimum heap
            if (node->key < min_heap->key )
            {
                    min_heap = node;
            }
 
    }
 
    void consolidate()
    {
          // Make sure the degree of each tree is unique
            heap_node* degree_nodes[max_degrees];
            heap_node* node = root_heap;
 
            memset(degree_nodes, 0, sizeof(degree_nodes));
            while (node != NULL)
            {
                    if (degree_nodes[node->degree] == NULL)
                    {
                            degree_nodes[node->degree] = node;
                            node = node->right;
                    }
                    else    // merge the two trees
                    {
                            heap_node* pre_node = degree_nodes[node->degree];
                            
                            if (node->key <pre_node->key)
                            {
                                    attach_tree(pre_node, node);
                            }
                            else
                            {
                                    attach_tree(node, pre_node);
                            }
 
                            // Reset the search
                            memset(degree_nodes, 0, sizeof(degree_nodes));                  
                            node = root_heap;
                    }
            }
 
    }
 
    void attach_tree(heap_node* from_node, heap_node* to_node)
    {
         if (from_node == root_heap)
            {
                    root_heap = root_heap->right;
            }
            
            // Break the link of from_node
            if (from_node->left)  from_node->left->right = from_node->right;
            if (from_node->right) from_node->right->left = from_node->left;
            from_node->left = NULL;
            from_node->right = NULL;
 
            // Move the from_node under the to_node
            to_node->children[ to_node->num_children ] = from_node;
            from_node->parent = to_node;
            to_node->num_children++;
            to_node->degree++;
 
    }
 
    void level_up(heap_node* node)
    {
         for (int i = 0; i < node->num_children; i++)
            {
                    heap_node* child_node = node->children[i];
 
                    add_to_root_heap(child_node);
                    child_node->parent = NULL;
                    node->children[i] = NULL;
            }
 
            node->num_children = 0;
 
    }
 
    void remove_node(heap_node* node)
    {
          if (node == NULL) return;
 
            if (node == root_heap)
            {
                    root_heap = root_heap->right;
            }
            if (node->left)  node->left->right = node->right;
            if (node->right) node->right->left = node->left;
            delete node;
 
    }
 
    void assign_min_node()
    {
          heap_node* check_node = root_heap;
 
            while (check_node != NULL)
            {
                    if (min_heap == NULL || check_node->key < min_heap->key )
                    {
                            min_heap = check_node;
                    }
                    
                    check_node = check_node->right;
            }
 
    }
 
    void delete_tree(heap_node* node)
    {
          if (node == NULL) return;
            
            for (int i = 0; i < node->num_children; i++)
            {
                    heap_node* child_node = node->children[i];
                    delete_tree(child_node);
            }
 
            delete node;
 
    }
};
 
    }
}