1
\$\begingroup\$

(See the previous iteration.)

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.)

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – greybeard Jan 31 '16 at 18:27
  • \$\begingroup\$ 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. \$\endgroup\$ – ChrisWue Jan 31 '16 at 21:18
  • \$\begingroup\$ You are restricting yourself to C89? \$\endgroup\$ – Deduplicator Jan 31 '16 at 22:23
1
\$\begingroup\$

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.

  1. 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.

  2. 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.

  3. 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;
        }
    }
    
  4. 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.

  5. 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);
    }
    
  6. 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.

\$\endgroup\$
  • \$\begingroup\$ Save a line or 2: in fibonacci_heap_node_free(), heap_node* sibling = child->right; in do loop. \$\endgroup\$ – chux Feb 2 '16 at 1:12
1
\$\begingroup\$

(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.)

\$\endgroup\$
  • \$\begingroup\$ (My C is rusty as last used in earnest in a millenium gone. My only C++ environment I remember working is for tinyAVR…) \$\endgroup\$ – greybeard Feb 1 '16 at 12:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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