summaryrefslogtreecommitdiff
path: root/cesar/lib/leftheap.h
diff options
context:
space:
mode:
Diffstat (limited to 'cesar/lib/leftheap.h')
-rw-r--r--cesar/lib/leftheap.h81
1 files changed, 81 insertions, 0 deletions
diff --git a/cesar/lib/leftheap.h b/cesar/lib/leftheap.h
new file mode 100644
index 0000000000..b2efd42cfe
--- /dev/null
+++ b/cesar/lib/leftheap.h
@@ -0,0 +1,81 @@
+#ifndef lib_leftheap_h
+#define lib_leftheap_h
+/* Cesar project {{{
+ *
+ * Copyright (C) 2007 Spidcom
+ *
+ * <<<Licence>>>
+ *
+ * }}} */
+/**
+ * \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 */