1//! @file heap.cpp
2//! @author ryftchen
3//! @brief The definitions (heap) in the data structure module.
4//! @version 0.1.0
5//! @copyright Copyright (c) 2022-2025 ryftchen. All rights reserved.
6
7#include "heap.hpp"
8
9#include <cstring>
10
11namespace data_structure::heap
12{
13//! @brief Function version number.
14//! @return version number (major.minor.patch)
15const char* version() noexcept
16{
17 static const char* const ver = "0.1.0";
18 return ver;
19}
20
21// NOLINTBEGIN(cppcoreguidelines-owning-memory, cppcoreguidelines-pro-type-const-cast)
22namespace binary
23{
24//! @brief Get the index of the key in the binary heap.
25//! @param heap - heap to search in
26//! @param key - key of the data
27//! @return index of the key if found, otherwise -1
28static int getIndex(const BinaryHeap* const heap, const void* const key)
29{
30 if (!heap || !key)
31 {
32 return -1;
33 }
34
35 for (int i = 0; i < heap->size; ++i)
36 {
37 if (heap->compare(heap->data[i], key) == 0)
38 {
39 return i;
40 }
41 }
42 return -1;
43}
44
45//! @brief Filter up the element at the specified index in the binary heap.
46//! @param heap - heap to filter in
47//! @param start - index to start filtering from
48static void filterUp(const BinaryHeap* const heap, const int start)
49{
50 if (!heap || (start < 0))
51 {
52 return;
53 }
54
55 int child = start;
56 int parent = (child - 1) / 2;
57 void* const temp = heap->data[child];
58 while (child > 0)
59 {
60 if (heap->compare(temp, heap->data[parent]) >= 0)
61 {
62 break;
63 }
64
65 heap->data[child] = heap->data[parent];
66 child = parent;
67 parent = (parent - 1) / 2;
68 }
69 heap->data[child] = temp;
70}
71
72//! @brief Filter down the element at the specified index in the binary heap.
73//! @param heap - heap to filter in
74//! @param start - index to start filtering from
75static void filterDown(const BinaryHeap* const heap, const int start)
76{
77 if (!heap || (start < 0))
78 {
79 return;
80 }
81
82 const int end = heap->size - 1;
83 int child = start;
84 int selected = (2 * child) + 1;
85 void* const temp = heap->data[child];
86 while (selected <= end)
87 {
88 if ((selected < end) && (heap->compare(heap->data[selected], heap->data[selected + 1]) > 0))
89 {
90 ++selected;
91 }
92 if (heap->compare(temp, heap->data[selected]) <= 0)
93 {
94 break;
95 }
96
97 heap->data[child] = heap->data[selected];
98 child = selected;
99 selected = 2 * selected + 1;
100 }
101 heap->data[child] = temp;
102}
103
104//! @brief Create the binary heap.
105//! @param cap - capacity of the heap
106//! @param cmp - compare function to compare keys
107//! @return new binary heap
108BinaryHeap* create(const int cap, const Compare cmp)
109{
110 if ((cap <= 0) || !cmp)
111 {
112 return nullptr;
113 }
114
115 auto* const heap = ::new (std::nothrow) BinaryHeap;
116 if (!heap)
117 {
118 return nullptr;
119 }
120 heap->data = ::new (std::nothrow) void*[cap];
121 if (!heap->data)
122 {
123 ::delete heap;
124 return nullptr;
125 }
126
127 std::memset(s: static_cast<void*>(heap->data), c: 0, n: sizeof(void*) * cap);
128 heap->capacity = cap;
129 heap->size = 0;
130 heap->compare = cmp;
131 return heap;
132}
133
134//! @brief Destroy the binary heap.
135//! @param heap - heap to destroy
136void destroy(BinaryHeap* heap)
137{
138 if (!heap)
139 {
140 return;
141 }
142
143 ::delete[] heap->data;
144 heap->data = nullptr;
145 ::delete heap;
146 heap = nullptr;
147}
148
149//! @brief Insert the data into the binary heap.
150//! @param heap - heap to insert into
151//! @param key - key of the data
152//! @return success or failure
153bool insert(BinaryHeap* const heap, const void* const key)
154{
155 if (!heap || !key || (heap->size >= heap->capacity))
156 {
157 return false;
158 }
159
160 heap->data[heap->size] = const_cast<void*>(key);
161 filterUp(heap, start: heap->size);
162 ++heap->size;
163 return true;
164}
165
166//! @brief Remove the data from the binary heap.
167//! @param heap - heap to remove from
168//! @param key - key of the data
169//! @return success or failure
170bool remove(BinaryHeap* const heap, const void* const key)
171{
172 if (!heap || !key || (heap->size == 0))
173 {
174 return false;
175 }
176
177 const int index = getIndex(heap, key);
178 if (index == -1)
179 {
180 return false;
181 }
182
183 heap->data[index] = heap->data[--heap->size];
184 filterDown(heap, start: index);
185 return true;
186}
187
188void Traverse::order(const Operation& op) const
189{
190 if (!heap || !op)
191 {
192 return;
193 }
194
195 for (int i = 0; i < heap->size; ++i)
196 {
197 op(heap->data[i]);
198 }
199}
200} // namespace binary
201
202namespace leftist
203{
204//! @brief Create the node of the leftist subheap.
205//! @param key - key of the node to be created
206//! @return new node after creating
207static Node* createNode(const void* const key)
208{
209 if (!key)
210 {
211 return nullptr;
212 }
213
214 Node* const newNode = ::new (std::nothrow) Node;
215 if (!newNode)
216 {
217 return nullptr;
218 }
219
220 newNode->left = newNode->right = nullptr;
221 newNode->key = const_cast<void*>(key);
222 newNode->npl = 0;
223 return newNode;
224}
225
226//! @brief Remove the node from the leftist subheap.
227//! @param node - target node
228static void removeNode(const Node* node)
229{
230 if (!node)
231 {
232 return;
233 }
234
235 removeNode(node: node->left);
236 removeNode(node: node->right);
237 ::delete node;
238 node = nullptr;
239}
240
241//! @brief Merge two nodes in the leftist subheap.
242//! @param d - destination node
243//! @param s - source node
244//! @param cmp - compare function to compare keys
245//! @return destination node after merging
246static Node* mergeNode(Node* d, Node* s, const CompareFunc cmp)
247{
248 if (!cmp)
249 {
250 return nullptr;
251 }
252 if (!d)
253 {
254 return s;
255 }
256 if (!s)
257 {
258 return d;
259 }
260
261 if (cmp(d->key, s->key) > 0)
262 {
263 Node* const temp = d;
264 d = s;
265 s = temp;
266 }
267
268 d->right = mergeNode(d: d->right, s, cmp);
269 if (!d->left || (d->left->npl < d->right->npl))
270 {
271 Node* const temp = d->left;
272 d->left = d->right;
273 d->right = temp;
274 }
275
276 if (!d->right || !d->left)
277 {
278 d->npl = 0;
279 }
280 else
281 {
282 d->npl = (d->right->npl < d->left->npl) ? (d->right->npl + 1) : (d->left->npl + 1);
283 }
284 return d;
285}
286
287//! @brief Get the node where the minimum key is located in the leftist heap.
288//! @param heap - leftist heap
289//! @return node where the minimum key is located
290void* getMinimum(const LeftistHeap* const heap)
291{
292 return (heap && heap->root) ? heap->root->key : nullptr;
293}
294
295//! @brief Create the leftist heap.
296//! @param cmp - compare function to compare keys
297//! @return new leftist heap
298LeftistHeap* create(const CompareFunc cmp)
299{
300 if (!cmp)
301 {
302 return nullptr;
303 }
304
305 auto* const heap = ::new (std::nothrow) LeftistHeap;
306 if (!heap)
307 {
308 return nullptr;
309 }
310
311 heap->root = nullptr;
312 heap->compare = cmp;
313 return heap;
314}
315
316//! @brief Destroy the leftist heap.
317//! @param heap - leftist heap
318void destroy(const LeftistHeap* heap)
319{
320 if (!heap)
321 {
322 return;
323 }
324
325 removeNode(node: heap->root);
326 ::delete heap;
327 heap = nullptr;
328}
329
330//! @brief Insert the node into the leftist heap.
331//! @param heap - leftist heap
332//! @param key - key of the target node
333void insert(LeftistHeap* const heap, const void* const key)
334{
335 if (!heap)
336 {
337 return;
338 }
339
340 Node* node = createNode(key);
341 if (!node)
342 {
343 return;
344 }
345
346 Node* const merged = mergeNode(d: heap->root, s: node, cmp: heap->compare);
347 if (!merged)
348 {
349 ::delete node;
350 node = nullptr;
351 return;
352 }
353 heap->root = merged;
354}
355
356//! @brief Remove the node where the minimum key is located from the leftist heap.
357//! @param heap - leftist heap
358void remove(LeftistHeap* const heap)
359{
360 if (!heap || !heap->root)
361 {
362 return;
363 }
364
365 Node* const left = heap->root->left;
366 Node* const right = heap->root->right;
367 ::delete heap->root;
368
369 heap->root = mergeNode(d: left, s: right, cmp: heap->compare);
370}
371
372//! @brief Merge the source leftist heap into the destination heap.
373//! @param dst - destination leftist heap
374//! @param src - source leftist heap
375void merge(LeftistHeap* const dst, LeftistHeap* const src)
376{
377 if (!dst || !src)
378 {
379 return;
380 }
381
382 dst->root = mergeNode(d: dst->root, s: src->root, cmp: dst->compare);
383 src->root = nullptr;
384}
385} // namespace leftist
386
387namespace skew
388{
389//! @brief Create the node of the skew subheap.
390//! @param key - key of the node to be created
391//! @return new node after creating
392static Node* createNode(const void* const key)
393{
394 if (!key)
395 {
396 return nullptr;
397 }
398
399 Node* const newNode = ::new (std::nothrow) Node;
400 if (!newNode)
401 {
402 return nullptr;
403 }
404
405 newNode->left = newNode->right = nullptr;
406 newNode->key = const_cast<void*>(key);
407 return newNode;
408}
409
410//! @brief Remove the node from the skew subheap.
411//! @param node - target node
412static void removeNode(const Node* node)
413{
414 if (!node)
415 {
416 return;
417 }
418
419 removeNode(node: node->left);
420 removeNode(node: node->right);
421 ::delete node;
422 node = nullptr;
423}
424
425//! @brief Merge two nodes in the skew subheap.
426//! @param d - destination node
427//! @param s - source node
428//! @param cmp - compare function to compare keys
429//! @return destination node after merging
430static Node* mergeNode(Node* d, Node* s, const CompareFunc cmp)
431{
432 if (!cmp)
433 {
434 return nullptr;
435 }
436 if (!d)
437 {
438 return s;
439 }
440 if (!s)
441 {
442 return d;
443 }
444
445 if (cmp(d->key, s->key) > 0)
446 {
447 Node* const temp = d;
448 d = s;
449 s = temp;
450 }
451
452 Node* const merged = mergeNode(d: d->right, s, cmp);
453 d->right = d->left;
454 d->left = merged;
455 return d;
456}
457
458//! @brief Create the skew heap.
459//! @param cmp - compare function to compare keys
460//! @return new skew heap
461SkewHeap* create(const CompareFunc cmp)
462{
463 if (!cmp)
464 {
465 return nullptr;
466 }
467
468 auto* const heap = ::new (std::nothrow) SkewHeap;
469 if (!heap)
470 {
471 return nullptr;
472 }
473
474 heap->root = nullptr;
475 heap->compare = cmp;
476 return heap;
477}
478
479//! @brief Destroy the skew heap.
480//! @param heap - skew heap
481void destroy(const SkewHeap* heap)
482{
483 if (!heap)
484 {
485 return;
486 }
487
488 removeNode(node: heap->root);
489 ::delete heap;
490 heap = nullptr;
491}
492
493//! @brief Insert the node into the skew heap.
494//! @param heap - skew heap
495//! @param key - key of the target node
496void insert(SkewHeap* const heap, const void* const key)
497{
498 if (!heap)
499 {
500 return;
501 }
502
503 Node* node = createNode(key);
504 if (!node)
505 {
506 return;
507 }
508
509 Node* const merged = mergeNode(d: heap->root, s: node, cmp: heap->compare);
510 if (!merged)
511 {
512 ::delete node;
513 node = nullptr;
514 return;
515 }
516 heap->root = merged;
517}
518
519//! @brief Remove the node with the minimum key from the skew heap.
520//! @param heap - target heap
521void remove(SkewHeap* const heap)
522{
523 if (!heap || !heap->root)
524 {
525 return;
526 }
527
528 Node* const left = heap->root->left;
529 Node* const right = heap->root->right;
530 ::delete heap->root;
531
532 heap->root = mergeNode(d: left, s: right, cmp: heap->compare);
533}
534
535//! @brief Get the minimum key from the skew heap.
536//! @param heap - target heap
537//! @return pointer to the minimum key, or nullptr if empty
538void* getMinimum(const SkewHeap* const heap)
539{
540 return (heap && heap->root) ? heap->root->key : nullptr;
541}
542
543//! @brief Merge the source skew heap into the destination heap.
544//! @param dst - destination skew heap
545//! @param src - source skew heap
546void merge(SkewHeap* const dst, SkewHeap* const src)
547{
548 if (!dst || !src)
549 {
550 return;
551 }
552
553 dst->root = mergeNode(d: dst->root, s: src->root, cmp: dst->compare);
554 src->root = nullptr;
555}
556} // namespace skew
557// NOLINTEND(cppcoreguidelines-owning-memory, cppcoreguidelines-pro-type-const-cast)
558} // namespace data_structure::heap
559