Fibonacci heap in C - follow-up

Question

I have incorporated some points made by ChrisWue and refactored my Fibonacci heap implementation:

fibonacci_heap.h

#ifndef FIBONACCI_HEAP_H
#define FIBONACCI_HEAP_H

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

#ifdef  __cplusplus
extern "C" {
#endif

    typedef struct fibonacci_heap fibonacci_heap;

    /***************************************************************************
    * Allocates a new empty Fibonacci heap.                                    *
    ***************************************************************************/  
    fibonacci_heap* 
    fibonacci_heap_alloc(size_t initial_capacity,
                         float  load_factor,
                         size_t (*hash_function)(void*),
                         bool   (*equals_function)(void*, void*),
                         int    (*priority_compare_function)(void*, void*));

    /***************************************************************************
    * Adds a new element and its priority to the heap only if it is not        *
    * already present.                                                         *
    ***************************************************************************/  
    bool fibonacci_heap_add(fibonacci_heap* heap, 
                            void* element, 
                            void* priority);

    /***************************************************************************
    * Attempts to assign a higher priority to the element. Returns true only   *       
    * if the structure of the heap changed due to this call.                   * 
    ***************************************************************************/  
    bool fibonacci_heap_decrease_key(fibonacci_heap* heap, 
                                     void* element, 
                                     void* priority);

    /***************************************************************************
    * Return true only if the element is in the heap.                          * 
    ***************************************************************************/  
    bool fibonacci_heap_contains_key(fibonacci_heap* heap, void* element);

    /***************************************************************************
    * Removes the highest priority element and returns it.                     * 
    ***************************************************************************/  
    void* fibonacci_heap_extract_min(fibonacci_heap* heap);

    /***************************************************************************
    * Returns the highest priority element without removing it.                * 
    ***************************************************************************/  
    void* fibonacci_heap_min(fibonacci_heap* heap);

    /***************************************************************************
    * Returns the size of this heap.                                           * 
    ***************************************************************************/  
    int fibonacci_heap_size(fibonacci_heap* heap);

    /***************************************************************************
    * Drops all the contents of the heap. Only internal structures are         *
    * deallocated; the user is responsible for memory-managing the contents.   * 
    ***************************************************************************/  
    void fibonacci_heap_clear(fibonacci_heap* heap);

    /***************************************************************************
    * Checks that the heap maintains the min-heap property.                    *
    ***************************************************************************/  
    bool fibonacci_heap_is_healthy(fibonacci_heap* heap);

    /***************************************************************************
    * Deallocates the entire heap with its internal structures. The client     *
    * programmer must, however, memory-manage the contents.                    * 
    ***************************************************************************/  
    void fibonacci_heap_free(fibonacci_heap* heap);

#ifdef  __cplusplus
}
#endif

#endif  /* HEAP_H */

fibonacci_heap.c

#include "fibonacci_heap.h"
#include "unordered_map.h"
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

static const double LOG_PHI = 0.4813;
static const size_t DEFAULT_NODE_ARRAY_CAPACITY = 8;

typedef struct heap_node {
    void*             element;
    void*             priority;
    struct heap_node* parent;
    struct heap_node* left;
    struct heap_node* right;
    struct heap_node* child;
    size_t            degree;
    bool              marked;
} heap_node;

struct fibonacci_heap {
    unordered_map_t* node_map;
    heap_node*       minimum_node;
    heap_node**      node_array;
    size_t           node_array_capacity;
    size_t         (*hash_function)(void*);
    bool           (*equals_function)(void*, void*);
    int            (*key_compare_function)(void*, void*);
};

static heap_node* fibonacci_heap_node_alloc(void* element, void* priority) {
    heap_node* node = malloc(sizeof(heap_node));

    if (!node) 
    {
        return NULL;
    }

    node->element  = element;
    node->priority = priority;
    node->parent   = NULL;
    node->left     = node;
    node->right    = node;
    node->child    = NULL;
    node->degree   = 0U;
    node->marked   = false;

    return node;
}

static void fibonacci_heap_node_free(heap_node* node) 
{
    heap_node* child;
    heap_node* first_child;
    heap_node* sibling;

    child = node->child;

    if (!child) 
    {
        free(node);
        return;
    }

    first_child = child;

    while (true)
    {
        sibling = child->right;
        fibonacci_heap_node_free(child);
        child = sibling;

        if (child == first_child) 
        {
            break;
        }
    }

    free(node);
}

fibonacci_heap* 
fibonacci_heap_alloc(size_t map_initial_capacity,
                     float map_load_factor,
                     size_t (*hash_function)(void*),
                     bool (*equals_function)(void*, void*),
                     int (*key_compare_function)(void*, void*))
{
    fibonacci_heap* heap;

    if (!hash_function)       
    {
        return NULL;
    }

    if (!equals_function)     
    {
        return NULL;
    }

    if (!key_compare_function) 
    {
        return NULL;
    }

    heap = malloc(sizeof(fibonacci_heap));

    if (!heap) 
    {
        return NULL;
    }

    heap->node_array = malloc(sizeof(heap_node*) * DEFAULT_NODE_ARRAY_CAPACITY);

    if (!heap->node_array) 
    {
        free(heap);
        return NULL;
    }

    heap->node_array_capacity = DEFAULT_NODE_ARRAY_CAPACITY;
    heap->node_map = unordered_map_t_alloc(map_initial_capacity, 
                                           map_load_factor, 
                                           hash_function, 
                                           equals_function);

    if (!heap->node_map)
    {
        free(heap->node_array);
        free(heap);
        return NULL;
    }

    heap->minimum_node         = NULL;
    heap->hash_function        = hash_function;
    heap->equals_function      = equals_function;
    heap->key_compare_function = key_compare_function;

    return heap;
}

bool fibonacci_heap_add(fibonacci_heap* heap, void* element, void* priority) 
{
    heap_node* node;

    if (!heap) {
        return false;
    }

    if (unordered_map_t_contains_key(heap->node_map, element))
    {
        return false;
    }

    node = fibonacci_heap_node_alloc(element, priority);

    if (!node){
        return false;
    }

    if (heap->minimum_node)
    {
        node->left = heap->minimum_node;
        node->right = heap->minimum_node->right;
        heap->minimum_node->right = node;
        node->right->left = node;

        if (heap->key_compare_function(priority, 
                                       heap->minimum_node->priority) < 0) 
        {
            heap->minimum_node = node;
        }
    } 
    else 
    {
        heap->minimum_node = node;
    }

    unordered_map_t_put(heap->node_map, element, node);
    return true;
}

static void cut(fibonacci_heap* heap, heap_node* x, heap_node* y)
{
    x->left->right = x->right;
    x->right->left = x->left;
    y->degree--;

    if (y->child == x) 
    {
        y->child = x->right;
    }

    if (y->degree == 0) 
    {
        y->child = NULL;
    }

    x->left = heap->minimum_node;
    x->right = heap->minimum_node->right;
    heap->minimum_node->right = x;
    x->right->left = x;

    x->parent = NULL;
    x->marked = false;
}

static void cascading_cut(fibonacci_heap* heap, heap_node* y)
{
    heap_node* z = y->parent;

    if (z)
    {
        if (y->marked)
        {
            cut(heap, y, z);
            cascading_cut(heap, z);
        }
        else 
        {
            y->marked = true;
        }
    }
}

bool fibonacci_heap_decrease_key(fibonacci_heap* heap, 
                                 void* element, 
                                 void* priority)
{
    heap_node* x;
    heap_node* y;

    if (!heap)
    {
        return false;
    }

    x = unordered_map_t_get(heap->node_map, element);

    if (!x) 
    {
        return false;
    }

    if (heap->key_compare_function(x->priority, priority) <= 0)
    {
        /* Cannot improve priority of the input element. */
        return false;
    }

    x->priority = priority;
    y = x->parent;

    if (y && heap->key_compare_function(x->priority, y->priority) < 0) 
    {
        cut(heap, x, y);
        cascading_cut(heap, y);
    }

    if (heap->key_compare_function(x->priority, heap->minimum_node->priority) < 0)
    {
        heap->minimum_node = x;
    }

    return true;
}

static bool try_expand_array(fibonacci_heap* heap, size_t size)
{
    if (heap->node_array_capacity < size) 
    {
        free(heap->node_array);
        heap->node_array = malloc(sizeof(heap_node*) * size);

        if (!heap->node_array) 
        {
            return false;
        }

        heap->node_array_capacity = size;
        return true;
    } 
    else 
    {
        return true;
    }
}

static void link(heap_node* y, heap_node* x)
{
    y->left->right = y->right;
    y->right->left = y->left;

    y->parent = x;

    if (!x->child)
    {
        x->child = y;
        y->right = y;
        y->left = y;
    }
    else
    {
        y->left = x->child;
        y->right = x->child->right;
        x->child->right = y;
        y->right->left = y;
    }

    x->degree++;
    y->marked = false;
}

static void consolidate(fibonacci_heap* heap)
{
    size_t array_size = (size_t)(floor
                                    (log(unordered_map_t_size(heap->node_map)) 
                                     / LOG_PHI)) + 1;
    size_t     number_of_roots;
    size_t     degree;
    size_t     i;
    heap_node* x;
    heap_node* y;
    heap_node* tmp;
    heap_node* next;

    try_expand_array(heap, array_size);

    /* Set the internal node array components to NULL. */
    memset(heap->node_array, 0, array_size * sizeof(heap_node*));

    number_of_roots = 0;
    x = heap->minimum_node;

    if (x) 
    {
        ++number_of_roots;
        x = x->right;

        while (x != heap->minimum_node)
        {
            ++number_of_roots;
            x = x->right;
        }
    }

    while (number_of_roots > 0) 
    {
        degree = x->degree;
        next = x->right;

        while(true)
        {
            y = heap->node_array[degree];

            if (!y) break;

            if (heap->key_compare_function(x->priority, 
                                               y->priority) > 0) 
            {
                tmp = y;
                y = x;
                x = tmp;
            }

            link(y, x);
            heap->node_array[degree] = NULL;
            ++degree;
        }

        heap->node_array[degree] = x;
        x = next;
        --number_of_roots;
    }

    heap->minimum_node = NULL;

    for (i = 0; i < array_size; ++i) 
    {
        y = heap->node_array[i];

        if (!y)
        {
            continue;
        }

        if (heap->minimum_node) 
        {
            y->left->right = y->right;
            y->right->left = y->left;

            y->left = heap->minimum_node;
            y->right = heap->minimum_node->right;
            heap->minimum_node->right = y;
            y->right->left = y;

            if (heap->key_compare_function(
                   y->priority, 
                   heap->minimum_node->priority) < 0)
            {
                heap->minimum_node = y;
            }
        }
        else
        {
            heap->minimum_node = y;
        }
    }
}

void* fibonacci_heap_extract_min(fibonacci_heap* heap)
{
    heap_node* z;
    heap_node* x;
    heap_node* tmp_right;
    heap_node* node_to_free;

    void* p_ret;
    size_t number_of_children;

    if (!heap) 
    {
        return NULL;
    }

    z = heap->minimum_node;

    if (!z) 
    {
        return NULL; /* Heap is empty. */
    }

    number_of_children = z->degree;
    x = z->child;

    while (number_of_children > 0) 
    {
        tmp_right = x->right;

        x->left->right = x->right;
        x->right->left = x->left;

        x->left = heap->minimum_node;
        x->right = heap->minimum_node->right;
        heap->minimum_node->right = x;
        x->right->left = x;

        x->parent = NULL;
        x = tmp_right;
        --number_of_children;
    }

    z->left->right = z->right;
    z->right->left = z->left;

    p_ret = heap->minimum_node->element;

    if (z == z->right)
    {
        node_to_free = heap->minimum_node;
        heap->minimum_node = NULL;
    }
    else 
    {
        node_to_free = heap->minimum_node;
        heap->minimum_node = z->right;
        consolidate(heap);
    }

    unordered_map_t_remove(heap->node_map, p_ret);
    free(node_to_free);
    return p_ret;
}

bool fibonacci_heap_contains_key(fibonacci_heap* heap, void* element)
{
    if (!heap) 
    {
        return false;
    }

    return unordered_map_t_contains_key(heap->node_map, element);
}

void* fibonacci_heap_min(fibonacci_heap* heap)
{
    if (!heap)    
    {
        return NULL;
    }

    if (heap->minimum_node) 
    {
        return heap->minimum_node->element;
    }

    return NULL;
}

int fibonacci_heap_size(fibonacci_heap* heap)
{
    if (!heap)
    {
        return 0;
    }

    return unordered_map_t_size(heap->node_map);
}

void fibonacci_heap_clear(fibonacci_heap* heap)
{
    heap_node* current;
    heap_node* sibling;
    heap_node* first_root;

    if (!heap) 
    {
        return;
    }

    if (!heap->minimum_node)
    {
        return;
    }

    current = heap->minimum_node;
    first_root = current;

    while (true)
    {
        sibling = current->right;
        fibonacci_heap_node_free(current);
        current = sibling;

        if (current == first_root)
        {
            break;
        }
    }

    heap->minimum_node = NULL;
    unordered_map_t_clear(heap->node_map);
}

static bool tree_is_healthy(fibonacci_heap* heap, heap_node* node)
{
    heap_node* begin;

    if (!node) 
    {
        return true;
    }

    begin = node;

    while (true) 
    {
        if (heap->key_compare_function(node->priority, 
                                       node->parent->priority) < 0) 
        {
            return false;
        }

        if (!tree_is_healthy(heap, node)) 
        {
            return false;
        }

        begin = begin->right;

        if (begin == node) 
        {
            return false;
        }
    }

    return true;
}

static bool check_root_list(fibonacci_heap* heap)
{
    heap_node* current = heap->minimum_node;

    while (true)
    {
        if (heap->key_compare_function(current->priority,
                                       heap->minimum_node->priority) < 0) 
        {
            return false;
        }

        current = current->right;

        if (current == heap->minimum_node) 
        {
            return true;
        }
    }
}

bool fibonacci_heap_is_healthy(fibonacci_heap* heap)
{
    heap_node* root;

    if (!heap)
    {
        return false;
    }

    if (!heap->minimum_node) 
    {
        return true;
    }

    /* Check that in the root list, 'minimum_node' points to the node
       with largest priority. 
     */
    if (!check_root_list(heap))
    {
        return false;
    }

    root = heap->minimum_node;

    /* Check that all trees are min-heap ordered: the priority of any child is
     * not higher than the priority of its parent. */
    while (root)
    {
        if (!tree_is_healthy(heap, root->child))
        {
            return false;
        }

        root = root->right;

        if (root == heap->minimum_node)
        {
            return true;
        }
    }

    return false;
}

void fibonacci_heap_free(fibonacci_heap* heap)
{
    if (!heap) 
    {
        return;
    }

    if (heap->node_array) 
    {
        free(heap->node_array);
    }

    fibonacci_heap_clear(heap);

    if (heap->node_map)
    {
        unordered_map_t_free(heap->node_map);
    }

    free(heap);
}

Did it improve at all? Please tell me what comes to mind. (Correctness test and peformance benchmark may be found here.)

I like the de-mangled names better - pretty much anything that facilitates reading. While ChrisWue is right about "brace consistency", I prefer a formatting easier on vertical space even outside SE. — greybeard, Jan 31, 2016 at 18:27
FWIW, I like this current style of bracing better, maybe because it's the most common one used in C# land which I spent most of my time in. — ChrisWue, Jan 31, 2016 at 21:18

greybeard · Accepted Answer · 2016-02-01 15:33:57Z

(Dare I mention comments, doxygen, or statement of purpose?)

No documentation of heap_node and fibonacci_heap in particular means not knowing if there are any invariants to keep (at least on return).

There is quite some open coding of doubly-linked list operations: use a library or try and factor out as much as possible (which only carries so far with intrusive lists/trees in a language not supporting OO).

Regarding the amount of lines: consolidate early outs, e.g.:

/** Allocates and initialises a fibonacci_heap. */
fibonacci_heap*
fibonacci_heap_alloc(size_t map_initial_capacity,
                     float map_load_factor,
                     size_t (*hash_function)(void*),
                     bool (*equals_function)(void*, void*),
                     int (*key_compare_function)(void*, void*))
{
    fibonacci_heap* heap;

    if (!hash_function
        || !equals_function
        || !key_compare_function
        || !(heap = malloc(sizeof(fibonacci_heap))))
    {
        return NULL;
    }

    heap->node_array = malloc(sizeof(heap_node*) * DEFAULT_NODE_ARRAY_CAPACITY);
 …

(in fibonacci_heap_decrease_key(heap, element, priority), I'd stop short of heap->key_compare_function(): the comment doesn't apply to the NULL-checks.)

try_expand_array(heap, size): I'd assign the malloc()-result to a local variable returning false if NULL, freeing and assigning to node_array otherwise. The else-branch could be merged with the last part of the then - I'd prefer an early-out, instead. (Naming: I'm spoiled by java.util.*.ensureCapacity)

An alternate name and rendition of link(child, parent):

/** Moves child from current list of siblings
 *  to the children of parent,
 *  not considering any former child->parent. */
static void adopt(heap_node* parent, heap_node* child)
{
    child->left->right = child->right;
    child->right->left = child->left;

    child->parent = parent;

    heap_node *left;

    if (!(left = parent->child))
    {
        parent->child = child->left = child->right = child;
    }
    else
    {
        child->left = left;
        child->right = left->right;
               left->right = child;
        child->right->left = child;
    }

    parent->degree++;
    child->marked = false;
}

consolidate(heap) is on the long side. If you factor out recreate_node_array() (under a better name), you can return early from that avoiding the repetition of ++number_of_roots;
x = x->right;.

Guess fibonacci_heap_extract_min(heap) confused me - oho: following the pseudo code in the Fibonacci heap chapter of CLRS quite closely (consider referring to that near the top of the questions).

/** Extracts minimum from heap. */
/* Consolidates the heap if not left empty. */
void* fibonacci_heap_extract_min(fibonacci_heap* heap)
{
    heap_node
        *const minimum,
        *const left,
        *const first_child;

    if (!heap
        || !(minimum = heap->minimum_node))
    {
        return NULL; /* Heap is empty. */
    }

    if (NULL != (first_child = minimum->child))
    {
    /* dissociate from children */
        heap_node *child = first_child;
        do
            child->parent = NULL;
        while (first_child != (child = child->right));
    }
    if (minimum != (left = minimum->left)) /* minimum has siblings */
    {
        heap_node *const right = minimum->right;
        if (first_child) /* minimum had children */
        {
        /* splice minimums children into its siblings */
            left->right = first_child;
            right->left = first_child->left;
            right->left->right = right;
            first_child->left = left;
        }
        else
        {
        /* yank minimum from siblings */
            left->right = right;
            right->left = left;
            first_child = right;
        }
    }
    void *const min_element = minimum->element;
    free(minimum);

    if (NULL != (heap->minimum_node = first_child))
    {
        consolidate(heap);
    }

    unordered_map_t_remove(heap->node_map, min_element);

    return min_element;
}

(Open coded tree operations - tell me.)

(My C is rusty as last used in earnest in a millenium gone. My only C++ environment I remember working is for tinyAVR…) — greybeard, Feb 1, 2016 at 12:56

ChrisWue · Accepted Answer · 2016-02-01 00:40:48Z

This is quite a long implementation (667 lines of code) and as such I'll concentrate a bit on reducing the amount of code this time.

fibonacci_heap_node_free can be improved by consolidating the function into a single return statement and turning the while(true) into a do {} while loop. Resulting code:

static void fibonacci_heap_node_free(heap_node* node) 
{
    heap_node* child = node->child;

    if (child) 
    {
        heap_node* first_child = child;
        heap_node* sibling;

        do
        {
            sibling = child->right;
            fibonacci_heap_node_free(child);
            child = sibling;
        } while (child != first_child);
    }

    free(node);
}

Reduced from 30 down to 19 lines and arguably easier to follow.

In fibonacci_heap_alloc I would condense the three function pointer checks into a single check since they all test extremely similar conditions. Eliminates another 10 lines of code.

The check-and-update-minimum-node code appears at least three times. It's sufficiently long and gnarly to read that I'd extract it into a separate method:

static void update_minimum_node(fibonacci_heap* heap, heap_node* node)
{
    if (heap->key_compare_function(node->priority, heap->minimum_node->priority) < 0)
    {
        heap->minimum_node = node;
    }
}

This code appears four times (in other places x or y are used instead of node but the assignments are the same):
```
node->left = heap->minimum_node;
node->right = heap->minimum_node->right;
heap->minimum_node->right = node;
node->right->left = node;
```
Should be refactored into a common method.

fibonacci_heap_clear doesn't clear the node_array. This probably won;t cause a problem but it would be more consistent to do so. It can also be condensed a bit by consolidating the NULL checks and turning the while(true) into a do {} while loop. Resulting code:

void fibonacci_heap_clear(fibonacci_heap* heap)
{
    heap_node* current;
    heap_node* first_root;

    if (!heap || !heap->minimum_node) 
    {
        return;
    }

    first_root = current = heap->minimum_node;

    do
    {
        heap_node* sibling = current->right;
        fibonacci_heap_node_free(current);
        current = sibling;
    } while (current != first_root);

    heap->minimum_node = NULL;
    unordered_map_t_clear(heap->node_map);
    memset(heap->node_array, 0, sizeof(heap_node*) * heap->node_array_capacity);
}

node_array should actually not be a member of the heap. It's only ever used in consolidate and that function is only called from fibonacci_heap_extract_min. The way it's used is as a temporary scratch pad and as such should just be a local variable in consolidate.

Save a line or 2: in fibonacci_heap_node_free(), heap_node* sibling = child->right; in do loop. — chux - Reinstate Monica, Feb 2, 2016 at 1:12

Stack Exchange Network

Fibonacci heap in C - follow-up

2 Answers 2

Your Answer

Not the answer you're looking for? Browse other questions tagged
algorithm
c
heap
priority-queue
or ask your own question.

Linked

Hot Network Questions

Fibonacci heap in C - follow-up

2 Answers 2

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged algorithmcheappriority-queue or ask your own question.

Linked

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
algorithm
c
heap
priority-queue
or ask your own question.