Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
PairingHeap.h
Go to the documentation of this file.
1
32#pragma once
33
35
36#include <functional>
37
38namespace ogdf {
39
40
42template<typename T>
44 template<typename, typename>
45 friend class PairingHeap;
46
47protected:
49
53
57};
58
60
69template<typename T, typename C>
70class PairingHeap : public HeapBase<PairingHeap<T, C>, PairingHeapNode<T>, T, C> {
72
73public:
80 explicit PairingHeap(const C& cmp = C(), int initialSize = -1);
81
88 virtual ~PairingHeap();
89
91 const T& top() const override;
92
99 PairingHeapNode<T>* push(const T& value) override;
100
106 void pop() override;
107
117 void decrease(PairingHeapNode<T>* heapNode, const T& value) override;
118
126 void merge(PairingHeap<T, C>& other) override;
127
134 const T& value(PairingHeapNode<T>* heapNode) const override { return heapNode->value; }
135
136private:
138
143
145 static void link(PairingHeapNode<T>* parent, PairingHeapNode<T>* child);
147 static void unlink(PairingHeapNode<T>* heapNode);
148
150 static void release(PairingHeapNode<T>* heapNode);
151};
152
153template<typename T, typename C>
154PairingHeap<T, C>::PairingHeap(const C& cmp, int /* unused parameter */)
155 : base_type(cmp), m_root(nullptr) { }
156
157template<typename T, typename C>
159 release(m_root);
160 m_root = nullptr;
161}
162
163template<typename T, typename C>
164inline const T& PairingHeap<T, C>::top() const {
165 OGDF_ASSERT(m_root != nullptr);
166 return m_root->value;
167}
168
169template<typename T, typename C>
172
173 m_root = m_root == nullptr ? heapNode : merge(m_root, heapNode);
174 return heapNode;
175}
176
177template<typename T, typename C>
179 PairingHeapNode<T>* children = m_root->child;
180 delete m_root;
181
182 m_root = pair(children);
183}
184
185template<typename T, typename C>
187 heapNode->value = value;
188 if (heapNode->prev != nullptr) {
189 unlink(heapNode);
190 m_root = merge(m_root, heapNode);
191 }
192}
193
194template<typename T, typename C>
196 m_root = merge(m_root, other.m_root);
197 other.m_root = nullptr;
198}
199
200template<typename T, typename C>
202 if (heapNode == nullptr) {
203 return nullptr;
204 }
205
206 /*
207 * We move towards the end of list counting elements along the way. We do
208 * this for two reasons: to know whether the list has even or odd number of
209 * elements and for possible speed up of going-back through the list (loop
210 * unrolling is not applicable for iterators but works for integers).
211 */
212 size_t children = 1;
214 while (it->next != nullptr) {
215 it = it->next;
216 children++;
217 }
218
219 PairingHeapNode<T>* result;
220
221 if (children % 2 == 1) {
222 PairingHeapNode<T>* a = it;
223 it = it->prev;
224 a->prev = a->next = nullptr;
225 result = a;
226 } else {
227 PairingHeapNode<T>*a = it, *b = it->prev;
228 it = it->prev->prev;
229 a->prev = a->next = b->prev = b->next = nullptr;
230 result = merge(a, b);
231 }
232
233 for (size_t i = 0; i < (children - 1) / 2; i++) {
234 PairingHeapNode<T>*a = it, *b = it->prev;
235 it = it->prev->prev;
236 a->prev = a->next = b->prev = b->next = nullptr;
237 result = merge(merge(a, b), result);
238 }
239
240 return result;
241}
242
243template<typename T, typename C>
245 if (this->comparator()(a->value, b->value)) {
246 link(a, b);
247 return a;
248 } else {
249 link(b, a);
250 return b;
251 }
252}
253
254template<typename T, typename C>
256 if (root->child != nullptr) {
257 child->next = root->child;
258 root->child->prev = child;
259 }
260 child->prev = root;
261 root->child = child;
262}
263
264template<typename T, typename C>
266 if (heapNode->prev->child == heapNode) {
267 heapNode->prev->child = heapNode->next;
268 } else {
269 heapNode->prev->next = heapNode->next;
270 }
271 if (heapNode->next != nullptr) {
272 heapNode->next->prev = heapNode->prev;
273 }
274 heapNode->prev = nullptr;
275 heapNode->next = nullptr;
276}
277
278template<typename T, typename C>
280 /*
281 * Recursive version of this function is infinitely prettier than that
282 * abomination. Please, make it prettier if you can.
283 */
285
286 if (it == nullptr) {
287 return;
288 }
289
290 for (;;) {
291 // Slide down as long as possible.
292 if (it->child != nullptr) {
293 it = it->child;
294 continue;
295 }
296 if (it->next != nullptr) {
297 it = it->next;
298 continue;
299 }
300
301 // Climb up until you find first non-visited node.
302 for (;;) {
303 PairingHeapNode<T>*curr = it, *prev = it->prev;
304 delete it;
305
306 if (prev == nullptr) {
307 return;
308 }
309 if (curr == prev->child && prev->next != nullptr) {
310 it = prev->next;
311 break;
312 } else {
313 it = prev;
314 }
315 }
316 }
317}
318
319}
Interface for heap implementations.
Common interface for all heap classes.
Definition HeapBase.h:50
Pairing heap implementation.
Definition PairingHeap.h:70
static void release(PairingHeapNode< T > *heapNode)
Releases memory occupied by list of heaps given as heapNode.
static void link(PairingHeapNode< T > *parent, PairingHeapNode< T > *child)
Makes child node a child of parent node.
PairingHeapNode< T > * m_root
Root node of the heap.
void merge(PairingHeap< T, C > &other) override
Merges in values of other heap.
PairingHeapNode< T > * push(const T &value) override
Inserts a new node with given value into a heap.
const T & top() const override
Returns reference to the top element in the heap.
PairingHeapNode< T > * pair(PairingHeapNode< T > *heapNode)
Pairs list of heaps given as heapNode. Returns resulting list.
void pop() override
Removes the top element from the heap.
PairingHeap(const C &cmp=C(), int initialSize=-1)
Creates empty pairing heap.
virtual ~PairingHeap()
Destructs pairing heap.
static void unlink(PairingHeapNode< T > *heapNode)
Removes heapNode from its parent children list.
void decrease(PairingHeapNode< T > *heapNode, const T &value) override
Decreases value of the given heapNode to value.
const T & value(PairingHeapNode< T > *heapNode) const override
Returns the value of the node.
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition basic.h:41
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.
Pairing heap node.
Definition PairingHeap.h:43
PairingHeapNode(const T &valueOfNode)
Creates heap node with a given valueOfNode.
Definition PairingHeap.h:55
PairingHeapNode< T > * next
Next sibling of the node.
Definition PairingHeap.h:51
PairingHeapNode< T > * child
First child of the node.
Definition PairingHeap.h:52
T value
Value contained in the node.
Definition PairingHeap.h:48
PairingHeapNode< T > * prev
Previous sibling of the node or parent.
Definition PairingHeap.h:50