Algorithms Library Toolkit
A toolkit for algorithms, especially for algorithms on formal languages
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Concepts
BinomialHeap.h
Go to the documentation of this file.
1
6#pragma once
7
8#include <stdexcept>
9
10namespace alib {
11
12// binomial heap used as mergeable priority queue
13template < typename T, typename Comparator = std::less < T > >
15public:
16
17 BinomialHeap ( Comparator comparator = Comparator ( ) ) : m_head( nullptr ), m_size( 0 ), m_comparator ( comparator ) {
18 }
19
20 ~BinomialHeap ( );
21
22 // inserts a node with new value into the heap
23 void insert ( const T & value );
24
25 // finds the maximum value in the heap
26 const T & getMax ( ) const {
27 return ( * searchMax ( const_cast < Node * * > ( & m_head ) ) )->value;
28 }
29
30 // finds and removes the maximum value from the heap
31 T extractMax ( );
32
33 // merges this heap with another heap (!! this is a DESTRUCTIVE merge, heap in argument will be cleared !!)
35
36 size_t size ( ) const {
37 return m_size;
38 }
39
40protected:
41
42 struct Node {
44 unsigned degree;
48 Node( const T & val, unsigned deg = 0, Node * par = nullptr, Node * chld = nullptr, Node * sib = nullptr )
49 : value ( val ), degree ( deg ), parent ( par ), child ( chld ), sibling ( sib ) { }
50 };
51
52 Node * m_head; //< head of a singly linked list of binomial trees
53 size_t m_size; //< count of elements stored in the heap
54 Comparator m_comparator; //< user-defined comparator function
55
56protected:
57
58 // deletes one linked list of binomial trees
59 void deleteTreeList( Node * head );
60
61 // searches the linked list and returns address of variable pointing to the node with maximum value
62 Node * * searchMax( Node * * head ) const;
63 // merges linked lists from 2 binomial heaps and returns address of head of the new linked list
64
65 Node * mergeHeaps( Node * head1, Node * head2 );
66 // merges 2 linked lists of binomial trees and sorts the trees by increasing degree
67
68 Node * mergeListsByDeg( Node * head1, Node * head2 );
69 // reverses a linked list
70
71 Node * reverseList( Node * head );
72 // links root of tree1 to root of tree2 (tree1 becomes child of tree2)
73 Node * linkTreeToTree( Node * root1, Node * root2 );
74
75};
76
77template < typename T, typename Comparator >
79 deleteTreeList( m_head );
80}
81
82template < typename T, typename Comparator >
84 while (head != nullptr) {
85 Node * sibling = head->sibling;
86 deleteTreeList( head->child );
87 delete head;
88 head = sibling;
89 }
90}
91
92template < typename T, typename Comparator >
94 Node * newNode = new Node( value, 0, nullptr, nullptr, nullptr );
95
96 m_head = mergeHeaps( m_head, newNode ); // merge the current heap with the newNode,
97 // as if the newNode was a single-element heap
98 m_size++;
99}
100
101template< typename T, typename Comparator >
103 if ( m_size == 0 )
104 throw std::out_of_range ( "Heap is empty." );
105
106 Node * * ptrToMax = searchMax( &m_head ); // find the node with maximum value
107 Node * max = *ptrToMax;
108
109 *ptrToMax = max->sibling; // disconnect it from the linked list
110
111 Node * chlHead = reverseList( max->child ); // merge them with the heap in reversed order
112 m_head = mergeHeaps( this->m_head, chlHead );
113
114 m_size--;
115 T maxVal = max->value;
116 delete max; // extract the value from node and return it
117 return maxVal;
118}
119
120template < typename T, typename Comparator >
122 if (this->m_comparator != that.m_comparator) // nodes of these heaps are sorted by different condition
123 throw std::logic_error("compare functions aren't equal, unable to merge");
124
125 this->m_head = mergeHeaps( this->m_head, that.m_head ); // move the other heap into this heap
126 that.m_head = nullptr;
127
128 this->m_size += that.m_size;
129 that.m_size = 0;
130}
131
132template < typename T, typename Comparator >
134 Node * max = *head, * * ptrToMax = head;
135 for (Node * actual = * head, * prev = nullptr; actual != nullptr; prev = actual, actual = actual->sibling) {
136 if ( m_comparator ( max->value, actual->value ) ) {
137 max = actual;
138 ptrToMax = &prev->sibling;
139 }
140 }
141 return ptrToMax;
142}
143
144template < typename T, typename Comparator >
146 if ( ! head1 )
147 return head2;
148
149 if ( ! head2 )
150 return head1;
151
152 head1 = mergeListsByDeg( head1, head2 ); // first, merge the lists of trees by their degrees
153
154 Node * actual = head1;
155 Node * * toLink = & head1;
156 while (actual->sibling) {
157 Node * next = actual->sibling;
158
159 if (actual->degree != next->degree || (next->sibling && next->sibling->degree == actual->degree)) {
160 toLink = &actual->sibling; // not merging trees with same degree
161 actual = next; // or postponing the merge by 1 iteration
162 } else if ( ! m_comparator ( actual->value, next->value ) ) {
163 actual->sibling = next->sibling; // merging 2 binomial trees with same degree
164 actual = linkTreeToTree( next, actual ); // 'next' becomes child of 'actual'
165 } else {
166 *toLink = next; // merging 2 binomial trees with same degree
167 actual = linkTreeToTree( actual, next ); // 'actual' becomes child of 'next'
168 }
169 }
170
171 return head1;
172}
173
174template < typename T, typename Comparator >
176 Node * newHead = nullptr;
177 Node * * toLink = &newHead;
178 while (head1 && head2) {
179 if (head1->degree < head2->degree) {
180 *toLink = head1; // linking node from first list
181 toLink = &head1->sibling; // and moving first pointer
182 head1 = head1->sibling;
183 } else {
184 *toLink = head2; // linking node from second list
185 toLink = &head2->sibling; // and moving second pointer
186 head2 = head2->sibling;
187 }
188 }
189 if (!head1)
190 *toLink = head2; // list1 ended, link the rest of list2
191 else
192 *toLink = head1; // list2 ended, link the rest of list1
193
194 return newHead;
195}
196
197template < typename T, typename Comparator >
199 Node * prev = nullptr;
200
201 while (head) {
202 Node * next = head->sibling;
203 head->sibling = prev;
204 prev = head;
205 head = next;
206 }
207
208 return prev;
209}
210
211template < typename T, typename Comparator >
213 root1->parent = root2;
214 root1->sibling = root2->child;
215 root2->child = root1;
216 root2->degree++;
217
218 return root2;
219}
220
221} /* namespace alib */
222
Definition: BinomialHeap.h:14
size_t m_size
Definition: BinomialHeap.h:53
Node * mergeListsByDeg(Node *head1, Node *head2)
Definition: BinomialHeap.h:175
Node ** searchMax(Node **head) const
Definition: BinomialHeap.h:133
BinomialHeap(Comparator comparator=Comparator())
Definition: BinomialHeap.h:17
Comparator m_comparator
Definition: BinomialHeap.h:54
Node * m_head
Definition: BinomialHeap.h:52
T extractMax()
Definition: BinomialHeap.h:102
void deleteTreeList(Node *head)
Definition: BinomialHeap.h:83
Node * mergeHeaps(Node *head1, Node *head2)
Definition: BinomialHeap.h:145
void insert(const T &value)
Definition: BinomialHeap.h:93
size_t size() const
Definition: BinomialHeap.h:36
Node * linkTreeToTree(Node *root1, Node *root2)
Definition: BinomialHeap.h:212
Node * reverseList(Node *head)
Definition: BinomialHeap.h:198
void mergeWith(BinomialHeap< T, Comparator > &&that)
Definition: BinomialHeap.h:121
const T & getMax() const
Definition: BinomialHeap.h:26
~BinomialHeap()
Definition: BinomialHeap.h:78
Definition: ExceptionHandler.cpp:13
constexpr const T & max(const T &a)
Root case of maximum computation. The maximum from one value is the value itself.
Definition: algorithm.hpp:278
Definition: BinomialHeap.h:42
Node * parent
Definition: BinomialHeap.h:45
Node * child
Definition: BinomialHeap.h:46
Node(const T &val, unsigned deg=0, Node *par=nullptr, Node *chld=nullptr, Node *sib=nullptr)
Definition: BinomialHeap.h:48
T value
Definition: BinomialHeap.h:43
unsigned degree
Definition: BinomialHeap.h:44
Node * sibling
Definition: BinomialHeap.h:47