-
Notifications
You must be signed in to change notification settings - Fork 0
/
pheap.h
101 lines (90 loc) · 3.69 KB
/
pheap.h
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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
/*
* This is free and unencumbered software released into the public domain.
*
* Anyone is free to copy, modify, publish, use, compile, sell, or distribute
* this software, either in source code form or as a compiled binary, for any
* purpose, commercial or non-commercial, and by any means.
*
* In jurisdictions that recognize copyright laws, the author or authors of this
* software dedicate any and all copyright interest in the software to the
* public domain. We make this dedication for the benefit of the public at large
* and to the detriment of our heirs and successors. We intend this dedication
* to be an overt act of relinquishment in perpetuity of all present and future
* rights to this software under copyright law.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
* AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
* ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*
* For more information, please refer to <http://unlicense.org>
*/
/**
* \file pheap.h
*
* \brief Arbitrarily large pairing heaps.
*
* A pairing heap is a heap data structure built using pointers that has
* relatively low asymptotic and practical performance. All operations have
* amortized asymptotic time equivalent to Fibonacci heaps, but with a much
* simpler implementation and lower constants.
*
* This implementation supports a min-heap without using any dynamic memory
* allocation (all memory is allocated by the caller), embedding pointers within
* container structures in order to simplify memory usage.
*
* Pairing heaps were invented by Fredman, Sedgewick, Sleator, and Tarjan,
* inspired by splay trees. For more information, see
* https://en.wikipedia.org/wiki/Pairing_heap
*
* \author Brian Kubisiak
*
* \copyright This is free and unencumbered software released into the public
* domain.
*/
#ifndef _PHEAP_H_
#define _PHEAP_H_
#include "list.h"
#include "utils.h"
/**
* \brief Node in a pairing heap.
*
* This node element can be embedded into another structure in order to add the
* structure to a pairing heap. Use #containerof() to get a pointer to the
* containing structure.
*
* Must be initialized with #pheap_elem_init() before it can be pushed onto a
* heap.
*/
struct pheap_elem
{
struct list children; /**< List of children of this node. */
struct list_elem child_le; /**< List element to add this node to its
parent's list. */
};
/**
* \brief Pairing heap structure.
*
* The heap contains a root node, which is the minimum of the heap, as well as a
* compare function for comparing two elements on the heap. The root node will,
* in turn, contain a list of its children, creating a recursive structure. Note
* that this structure is used as a container for binding the compare function
* to each node in the heap.
*
* Must be initialized with #pheap_init() before it can be used.
*/
struct pheap
{
struct pheap_elem *root; /**< Root (minimum) element of the heap. */
cmp_func cmp; /**< Function for comparing two elements. */
};
void pheap_elem_init(struct pheap_elem *pe);
void pheap_init(struct pheap *ph, cmp_func cmp);
struct pheap_elem *pheap_peek(const struct pheap *ph);
void pheap_push(struct pheap *ph, struct pheap_elem *pe);
struct pheap_elem *pheap_pop(struct pheap *ph);
void pheap_merge(struct pheap *dst, struct pheap *src);
int pheap_isempty(struct pheap *ph);
#endif /* end of include guard: _PHEAP_H_ */