#ifndef lib_skewheap_h #define lib_skewheap_h /* Cesar project {{{ * * Copyright (C) 2007 Spidcom * * <<>> * * }}} */ /** * \file lib/skewheap.h * \brief Skew heaps. * \ingroup lib * * Skew heaps were invented by Daniel Dominic Sleator and Robert Endre Tarjan. * Skew heaps do not define any constrain on the tree structure. All * operations should use the skew merge. * * The skew merge operation merges the right paths of the two heaps to be * merged and swap all right and left children. The idea is that the right * path will be long after a merge. */ /** Heap node. */ struct heap_node_t { /** Pointer to parrent node. */ struct heap_node_t *father; /** Pointer to left and right children. */ struct heap_node_t *left, *right; }; 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_skewheap_h */