Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

BinomialHeap.h
Go to the documentation of this file.
1 
32 #pragma once
33 
34 #include <functional>
35 #include <utility>
36 
38 
39 namespace ogdf {
40 
41 
43 template<typename T>
45  template<typename, typename> friend class BinomialHeap;
46 protected:
47  T value;
48 
49  size_t rank;
50 
54 
56  explicit BinomialHeapNode(const T &nodeValue)
57  : value(nodeValue),
58  rank(0), parent(nullptr), next(nullptr), child(nullptr)
59  {
60  }
61 };
62 
63 
65 
74 template<typename T, typename C = std::less<T>>
75 class BinomialHeap : public HeapBase<BinomialHeap<T, C>, BinomialHeapNode<T>, T, C>
76 {
77 
79 
80 public:
81 
88  explicit BinomialHeap(const C &cmp = C(), int initialSize = -1);
89 
96  virtual ~BinomialHeap();
97 
99  const T &top() const override;
100 
107  BinomialHeapNode<T> *push(const T &value) override;
108 
114  void pop() override;
115 
125  void decrease(BinomialHeapNode<T> *heapNode, const T &value) override;
126 
134  void merge(BinomialHeap<T, C> &other) override;
135 
142  const T &value(BinomialHeapNode<T> *heapNode) const override {
143  return heapNode->value;
144  }
145 
146 private:
148 
152  void merge(BinomialHeapNode<T> *other);
153 
155  static void link(BinomialHeapNode<T> *parent, BinomialHeapNode<T> *child);
156 
158  static void release(BinomialHeapNode<T> *heapNode);
159 };
160 
161 
162 template<typename T, typename C>
163 BinomialHeap<T, C>::BinomialHeap(const C &cmp, int /* unused parameter */)
164 : base_type(cmp), m_root(nullptr) {}
165 
166 
167 template<typename T, typename C>
169 {
170  release(m_root);
171  m_root = nullptr;
172 }
173 
174 
175 template<typename T, typename C>
177 {
178  while(heapNode != nullptr) {
179  release(heapNode->child);
180 
181  BinomialHeapNode<T> *next = heapNode->next;
182  delete heapNode;
183  heapNode = next;
184  }
185 }
186 
187 
188 template<typename T, typename C>
189 inline const T &BinomialHeap<T, C>::top() const
190 {
191  BinomialHeapNode<T> *min = m_root;
192  for(BinomialHeapNode<T> *it = m_root->next; it != nullptr; it = it->next) {
193  if(this->comparator()(it->value, min->value)) {
194  min = it;
195  }
196  }
197 
198  return min->value;
199 }
200 
201 
202 template<typename T, typename C>
204 {
205  BinomialHeapNode<T> *heapNode = new BinomialHeapNode<T>(value);
206 
207  merge(heapNode);
208  return heapNode;
209 }
210 
211 
212 template<typename T, typename C>
214 {
215  BinomialHeapNode<T> *curr = m_root, *min = m_root, *minPrev = nullptr;
216 
217  while(curr->next != nullptr) {
218  if(this->comparator()(curr->next->value, min->value)) {
219  min = curr->next;
220  minPrev = curr;
221  }
222  curr = curr->next;
223  }
224 
225  if(min == m_root) {
226  m_root = min->next;
227  } else {
228  minPrev->next = min->next;
229  }
230 
231  // Children list has to be reversed before it can be merged.
232  BinomialHeapNode<T> *reversed = nullptr, *child = min->child;
233  while(child != nullptr) {
234  BinomialHeapNode<T> *next = child->next;
235  child->next = reversed;
236  reversed = child;
237  child = next;
238  }
239  merge(reversed);
240  delete min;
241 }
242 
243 
244 template<typename T, typename C>
245 void BinomialHeap<T, C>::decrease(BinomialHeapNode<T> *heapNode, const T &value)
246 {
247  // BinomialHeap::decrease is not supported
248  OGDF_ASSERT(false);
249 
250  heapNode->value = value;
251 
252  while(heapNode->parent != nullptr &&
253  this->comparator()(heapNode->value, heapNode->parent->value))
254  {
255  std::swap(heapNode->value, heapNode->parent->value);
256  heapNode = heapNode->parent;
257  }
258 }
259 
260 
261 template<typename T, typename C>
263 {
264  merge(other.m_root);
265  other.m_root = nullptr;
266 }
267 
268 
269 template<typename T, typename C>
272 {
273  if(a == nullptr) {
274  return b;
275  }
276  if(b == nullptr) {
277  return a;
278  }
279 
280  if(b->rank < a->rank) {
281  std::swap(a, b);
282  }
283 
284  BinomialHeapNode<T> *head = a;
285  while(b != nullptr) {
286  if(a->next == nullptr) {
287  a->next = b;
288  break;
289  }
290 
291  if(b->rank < a->next->rank) {
292  BinomialHeapNode<T> *nextB = b->next;
293  b->next = a->next;
294  a->next = b;
295 
296  a = b;
297  b = nextB;
298  } else {
299  a = a->next;
300  }
301  }
302 
303  return head;
304 }
305 
306 
307 template<typename T, typename C>
309 {
310  m_root = join(m_root, other);
311  if(m_root == nullptr) {
312  return;
313  }
314 
315  BinomialHeapNode<T> *prev = nullptr, *curr = m_root, *next = m_root->next;
316  while(next != nullptr) {
317  if(curr->rank != next->rank || (next->next != nullptr &&
318  next->next->rank == curr->rank))
319  {
320  prev = curr;
321  curr = next;
322  next = curr->next;
323  continue;
324  }
325 
326  if(this->comparator()(curr->value, next->value)) {
327  curr->next = next->next;
328  link(curr, next);
329  } else if(prev == nullptr) {
330  m_root = next;
331  link(next, curr);
332  curr = next;
333  } else {
334  prev->next = next;
335  link(next, curr);
336  curr = next;
337  }
338  next = curr->next;
339  }
340 }
341 
342 
343 template<typename T, typename C>
346 {
347  child->next = parent->child;
348  child->parent = parent;
349  parent->child = child;
350  parent->rank++;
351 }
352 
353 }
ogdf
The namespace for all OGDF objects.
Definition: AugmentationModule.h:36
ogdf::BinomialHeap::value
const T & value(BinomialHeapNode< T > *heapNode) const override
Returns the value of the node.
Definition: BinomialHeap.h:142
ogdf::HeapBase
Common interface for all heap classes.
Definition: HeapBase.h:55
OGDF_ASSERT
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition: basic.h:41
ogdf::BinomialHeap::decrease
void decrease(BinomialHeapNode< T > *heapNode, const T &value) override
Decreases value of the given heapNode to value.
Definition: BinomialHeap.h:245
ogdf::BinomialHeapNode::rank
size_t rank
Determines rank of a node.
Definition: BinomialHeap.h:49
ogdf::BinomialHeapNode::child
BinomialHeapNode< T > * child
First child of the node.
Definition: BinomialHeap.h:53
ogdf::BinomialHeap::top
const T & top() const override
Returns reference to the top element in the heap.
Definition: BinomialHeap.h:189
ogdf::BinomialHeap
Binomial heap implementation.
Definition: BinomialHeap.h:75
ogdf::BinomialHeap::release
static void release(BinomialHeapNode< T > *heapNode)
Releases memory occupied by list of heaps given as heapNode.
Definition: BinomialHeap.h:176
ogdf::BinomialHeapNode
Binomial heap node.
Definition: BinomialHeap.h:44
ogdf::BinomialHeap::push
BinomialHeapNode< T > * push(const T &value) override
Inserts a new node with given value into a heap.
Definition: BinomialHeap.h:203
ogdf::BinomialHeap::join
BinomialHeapNode< T > * join(BinomialHeapNode< T > *a, BinomialHeapNode< T > *b)
Joins heap lists a and b into single list sorted by the ranks.
Definition: BinomialHeap.h:270
ogdf::BinomialHeap::m_root
BinomialHeapNode< T > * m_root
Root node of the heap.
Definition: BinomialHeap.h:147
ogdf::BinomialHeap::~BinomialHeap
virtual ~BinomialHeap()
Destructs the heap.
Definition: BinomialHeap.h:168
ogdf::BinomialHeap::BinomialHeap
BinomialHeap(const C &cmp=C(), int initialSize=-1)
Creates empty binomial heap.
Definition: BinomialHeap.h:163
ogdf::BinomialHeapNode::value
T value
Value contained in the node.
Definition: BinomialHeap.h:47
HeapBase.h
Interface for heap implementations.
ogdf::BinomialHeapNode::BinomialHeapNode
BinomialHeapNode(const T &nodeValue)
Creates heap node with a given nodeValue.
Definition: BinomialHeap.h:56
ogdf::BinomialHeap::pop
void pop() override
Removes the top element from the heap.
Definition: BinomialHeap.h:213
ogdf::BinomialHeap::link
static void link(BinomialHeapNode< T > *parent, BinomialHeapNode< T > *child)
Makes child node a child of parent node.
Definition: BinomialHeap.h:344
ogdf::BinomialHeap::merge
void merge(BinomialHeap< T, C > &other) override
Merges in values of other heap.
Definition: BinomialHeap.h:262
ogdf::BinomialHeapNode::next
BinomialHeapNode< T > * next
Next sibling of the node.
Definition: BinomialHeap.h:52
ogdf::BinomialHeapNode::parent
BinomialHeapNode< T > * parent
Parent of the node.
Definition: BinomialHeap.h:51