summaryrefslogtreecommitdiff
path: root/cesar/lib/leftheap.h
blob: b2efd42cfeebe6c5c21e032d7aa828db3c77344b (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
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 */