1//! @file heap.hpp
2//! @author ryftchen
3//! @brief The declarations (heap) in the data structure module.
4//! @version 0.1.0
5//! @copyright Copyright (c) 2022-2026 ryftchen. All rights reserved.
6
7#pragma once
8
9#include <functional>
10#include <ostream>
11
12//! @brief The data structure module.
13namespace data_structure // NOLINT(modernize-concat-nested-namespaces)
14{
15//! @brief Heap-related functions in the data structure module.
16namespace heap
17{
18//! @brief Brief function description.
19//! @return function description (module_function)
20inline static const char* description() noexcept
21{
22 return "DS_HEAP";
23}
24extern const char* version() noexcept;
25
26//! @brief The binary heap (min heap).
27namespace binary
28{
29#ifdef __cplusplus
30extern "C"
31{
32#endif
33 //! @brief Alias for the compare function type.
34 typedef int (*Compare)(const void* const, const void* const);
35
36#pragma pack(push, 8)
37 //! @brief The binary heap structure.
38 struct BinaryHeap
39 {
40 //! @brief Pointer to the data array.
41 void** data;
42 //! @brief The capacity of the heap.
43 int capacity;
44 //! @brief The current size of the heap.
45 int size;
46 //! @brief The key's compare function.
47 Compare compare;
48 };
49#pragma pack(pop)
50#ifdef __cplusplus
51}
52#endif
53
54extern BinaryHeap* create(const int cap, const Compare cmp);
55extern void destroy(BinaryHeap* heap);
56extern bool insert(BinaryHeap* const heap, const void* const key);
57extern bool remove(BinaryHeap* const heap, const void* const key);
58
59//! @brief Do traversing.
60class Traverse
61{
62public:
63 //! @brief Construct a new Traverse object.
64 //! @param heap - heap structure to be traversed
65 explicit Traverse(const BinaryHeap* const heap) : heap{heap} {}
66
67 //! @brief Alias for the operation when traversing.
68 using Operation = std::function<void(const void* const)>;
69 //! @brief Perform a order traversal starting from head.
70 //! @param op - operation on each node
71 void order(const Operation& op) const;
72
73private:
74 //! @brief The heap structure to be traversed.
75 const BinaryHeap* const heap{nullptr};
76};
77} // namespace binary
78
79//! @brief The leftist heap.
80namespace leftist
81{
82#ifdef __cplusplus
83extern "C"
84{
85#endif
86 //! @brief Alias for the compare function type.
87 typedef int (*CompareFunc)(const void* const, const void* const);
88
89#pragma pack(push, 8)
90 //! @brief The node of the leftist heap.
91 typedef struct LeftistNode
92 {
93 //! @brief Pointer to the left child node.
94 struct LeftistNode* left;
95 //! @brief Pointer to the right child node.
96 struct LeftistNode* right;
97 //! @brief Key value.
98 void* key;
99 //! @brief The null path length.
100 int npl;
101 } Node;
102
103 //! @brief The leftist heap structure.
104 struct LeftistHeap
105 {
106 //! @brief Pointer to the root node.
107 LeftistNode* root;
108 //! @brief The key's compare function.
109 CompareFunc compare;
110 };
111#pragma pack(pop)
112#ifdef __cplusplus
113}
114#endif
115
116void* getMinimum(const LeftistHeap* const heap);
117
118LeftistHeap* create(const CompareFunc cmp);
119void destroy(const LeftistHeap* heap);
120void insert(LeftistHeap* const heap, const void* const key);
121void remove(LeftistHeap* const heap);
122void merge(LeftistHeap* const dst, LeftistHeap* const src);
123} // namespace leftist
124
125//! @brief The skew heap.
126namespace skew
127{
128#ifdef __cplusplus
129extern "C"
130{
131#endif
132 //! @brief Alias for the compare function type.
133 typedef int (*CompareFunc)(const void* const, const void* const);
134
135#pragma pack(push, 8)
136 //! @brief The node of the skew heap.
137 typedef struct SkewNode
138 {
139 //! @brief Pointer to the left child node.
140 struct SkewNode* left;
141 //! @brief Pointer to the right child node.
142 struct SkewNode* right;
143 //! @brief Key value.
144 void* key;
145 } Node;
146
147 //! @brief The leftist heap structure.
148 struct SkewHeap
149 {
150 //! @brief Pointer to the root node.
151 SkewNode* root;
152 //! @brief The key's compare function.
153 CompareFunc compare;
154 };
155#pragma pack(pop)
156#ifdef __cplusplus
157}
158#endif
159
160void* getMinimum(const SkewHeap* const heap);
161
162SkewHeap* create(const CompareFunc cmp);
163void destroy(const SkewHeap* heap);
164void insert(SkewHeap* const heap, const void* const key);
165void remove(SkewHeap* const heap);
166void merge(SkewHeap* const dst, SkewHeap* const src);
167} // namespace skew
168
169//! @brief Do traversing.
170//! @tparam Heap - type of heap node
171//! @tparam Node - type of heap node
172template <typename Heap, typename Node>
173class Traverse
174{
175public:
176 //! @brief Construct a new Traverse object.
177 //! @param heap - heap structure to be traversed
178 explicit Traverse(const Heap* const heap) : heap{heap} {}
179
180 //! @brief Alias for the operation when traversing.
181 using Operation = std::function<void(const void* const)>;
182 //! @brief Perform a pre-order traversal of the heap.
183 //! @param op - operation on each node
184 void preOrder(const Operation& op) const;
185 //! @brief Perform a in-order traversal of the heap.
186 //! @param op - operation on each node
187 void inOrder(const Operation& op) const;
188 //! @brief Perform a post-order traversal of the heap.
189 //! @param op - operation on each node
190 void postOrder(const Operation& op) const;
191
192private:
193 //! @brief The heap structure to be traversed.
194 const Heap* const heap{nullptr};
195 //! @brief Perform a pre-order traversal of the subheap.
196 //! @param node - root of the subheap
197 //! @param op - operation on each node
198 static void preOrderTraversal(const Node* const node, const Operation& op);
199 //! @brief Perform a in-order traversal of the subheap.
200 //! @param node - root of the subheap
201 //! @param op - operation on each node
202 static void inOrderTraversal(const Node* const node, const Operation& op);
203 //! @brief Perform a post-order traversal of the subheap.
204 //! @param node - root of the subheap
205 //! @param op - operation on each node
206 static void postOrderTraversal(const Node* const node, const Operation& op);
207};
208
209template <typename Heap, typename Node>
210void Traverse<Heap, Node>::preOrder(const Operation& op) const
211{
212 if (!heap || !op)
213 {
214 return;
215 }
216
217 preOrderTraversal(node: heap->root, op);
218}
219
220template <typename Heap, typename Node>
221void Traverse<Heap, Node>::inOrder(const Operation& op) const
222{
223 if (!heap || !op)
224 {
225 return;
226 }
227
228 inOrderTraversal(node: heap->root, op);
229}
230
231template <typename Heap, typename Node>
232void Traverse<Heap, Node>::postOrder(const Operation& op) const
233{
234 if (!heap || !op)
235 {
236 return;
237 }
238
239 postOrderTraversal(node: heap->root, op);
240}
241
242template <typename Heap, typename Node>
243void Traverse<Heap, Node>::preOrderTraversal(const Node* const node, const Operation& op)
244{
245 if (!node)
246 {
247 return;
248 }
249
250 op(node->key);
251 preOrderTraversal(node: node->left, op);
252 preOrderTraversal(node: node->right, op);
253}
254
255template <typename Heap, typename Node>
256void Traverse<Heap, Node>::inOrderTraversal(const Node* const node, const Operation& op)
257{
258 if (!node)
259 {
260 return;
261 }
262
263 inOrderTraversal(node: node->left, op);
264 op(node->key);
265 inOrderTraversal(node: node->right, op);
266}
267
268template <typename Heap, typename Node>
269void Traverse<Heap, Node>::postOrderTraversal(const Node* const node, const Operation& op)
270{
271 if (!node)
272 {
273 return;
274 }
275
276 postOrderTraversal(node: node->left, op);
277 postOrderTraversal(node: node->right, op);
278 op(node->key);
279}
280
281//! @brief Print the heap structure.
282//! @tparam Node - type of heap node
283//! @tparam Key - type of node key
284template <typename Node, typename Key>
285class Printer
286{
287public:
288 //! @brief Construct a new Printer object.
289 //! @param root - root of the heap
290 explicit Printer(const Node* const root) : root{root} {}
291
292 //! @brief Print the node in the heap.
293 //! @param os - output stream object
294 //! @param node - root of the subheap
295 //! @param key - key of the node
296 //! @param direction - node type, the left is -1, the root is 0, and the right is 1
297 void printNode(std::ostream& os, const Node* const node, const void* const key, const int direction) const;
298
299private:
300 //! @brief The root of the heap.
301 const Node* const root{nullptr};
302 //! @brief Indentation size.
303 mutable int indent{0};
304
305protected:
306 template <typename HN, typename NK>
307 friend std::ostream& operator<<(std::ostream&, const Printer<HN, NK>&);
308};
309
310template <typename Node, typename Key>
311void Printer<Node, Key>::printNode(
312 std::ostream& os, const Node* const node, const void* const key, const int direction) const
313{
314 if (!node || !key)
315 {
316 return;
317 }
318
319 const int currInd = indent;
320 const Key nodeKey = *static_cast<const Key*>(node->key);
321 std::string ext{};
322 if constexpr (std::is_same_v<Node, leftist::Node>)
323 {
324 ext = '(' + std::to_string(node->npl) + ')';
325 }
326 if (direction == 0)
327 {
328 indent = 0;
329 os << "+ " << nodeKey << ext << " -> root\n";
330 }
331 else
332 {
333 os << "+ " << std::string(currInd, ' ') << nodeKey << ext << " -> " << *static_cast<const Key*>(key) << "'s "
334 << ((direction == 1) ? "right" : "left") << " child\n";
335 }
336
337 indent += 2;
338 printNode(os, node: node->left, key: node->key, direction: -1);
339 printNode(os, node: node->right, key: node->key, direction: 1);
340 indent = currInd;
341}
342
343//! @brief The operator (<<) overloading of the Printer class.
344//! @tparam HN - type of heap node
345//! @tparam NK - type of node key
346//! @param os - output stream object
347//! @param printer - specific Printer object
348//! @return reference of the output stream object
349template <typename HN, typename NK>
350std::ostream& operator<<(std::ostream& os, const Printer<HN, NK>& printer)
351{
352 if (printer.root)
353 {
354 printer.printNode(os, printer.root, printer.root->key, 0);
355 }
356 return os;
357}
358} // namespace heap
359} // namespace data_structure
360