#ifndef lib_leftheap_h #define lib_leftheap_h /* Cesar project {{{ * * Copyright (C) 2007 Spidcom * * <<>> * * }}} */ /** * \file lib/leftheap.h * \brief Leftist heaps. * \ingroup lib * * Leftist heaps were invented by Clark Allan Crane. This heap structure has * the particularity to be very unbalanced, where the shortest path to an * external node is always to the right. * * All operations are defined using the merge operation which operates O(log * n). The merge operation walks the right path (remember it is the shortest) * and merge with the heap to be merged, swapping left and right children as * needed. */ /** Heap node. */ struct heap_node_t { /** Pointer to parent node. */ struct heap_node_t *father; /** Pointer to left and right children. */ struct heap_node_t *left, *right; /** Shortest path to a external node. */ uint null_path_length; }; BEGIN_DECLS /** * Initialise an heap node. * \param node the node to initialise */ void heap_node_init (heap_node_t *node); /** * Merge two heaps rooted at the given nodes. * \param root1 the first heap root * \param root2 the second heap root (surprise!) * \param less comparison function * \return the new root node. */ heap_node_t * heap_node_merge (heap_node_t *root1, heap_node_t *root2, heap_node_less_t less); /** * Insert a new node in the given heap. * \param heap the heap * \param node the node to insert */ void heap_insert (heap_t *heap, heap_node_t *node); /** * Remove the heap root. * \param heap the heap */ void heap_remove_root (heap_t *heap); /** * Remove an arbitrary element * \param heap the heap * \param node the node to remove */ void heap_remove (heap_t *heap, heap_node_t *node); END_DECLS #endif /* lib_leftheap_h */