summaryrefslogtreecommitdiff
path: root/cesar/lib/skewheap.h
blob: ad095f43a547e4ea9ab3732be3927ed6eee39cfd (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
#ifndef lib_skewheap_h
#define lib_skewheap_h
/* Cesar project {{{
 *
 * Copyright (C) 2007 Spidcom
 *
 * <<<Licence>>>
 *
 * }}} */
/**
 * \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 */