32 #ifndef VPSC_PAIRING_HEAP_H 33 #define VPSC_PAIRING_HEAP_H 40 #include "libvpsc/assertions.h" 65 PairNode *nextSibling;
68 PairNode(
const T & theElement ) :
69 element( theElement ),
70 leftChild(nullptr), nextSibling(nullptr), prev(nullptr)
74 template <
class T,
class TCompare>
77 template <
class T,
class TCompare>
78 std::ostream& operator <<(std::ostream &os, const PairingHeap<T,TCompare> &b);
80 template <
class T,
class TCompare = std::less<T> >
84 friend std::ostream& operator<< <T,TCompare> (std::ostream &os,
const PairingHeap<T,TCompare> &b);
87 PairingHeap() : root(nullptr), counter(0), siblingsTreeArray(5) { }
88 PairingHeap(
const PairingHeap & rhs) {
92 ~PairingHeap() { makeEmpty(); }
93 const PairingHeap & operator=(
const PairingHeap & rhs );
94 bool isEmpty()
const {
return root ==
nullptr; }
95 unsigned size()
const {
return counter; }
96 PairNode<T> *insert(
const T & x );
97 const T & findMin( )
const;
99 const T extractMin( ) {
109 void decreaseKey( PairNode<T> *p,
const T & newVal );
110 void merge( PairingHeap<T,TCompare> *rhs );
113 PairNode<T> * removeRootForMerge(
unsigned& size) {
127 std::vector<PairNode<T> *> siblingsTreeArray;
129 void reclaimMemory( PairNode<T> *t )
const;
130 void compareAndLink( PairNode<T> * & first, PairNode<T> *second )
const;
131 PairNode<T> * combineSiblings( PairNode<T> *firstSibling );
132 PairNode<T> * clone( PairNode<T> * t )
const;
140 template <
class T,
class TCompare>
142 PairingHeap<T,TCompare>::insert(
const T & x )
144 PairNode<T> *newNode =
new PairNode<T>( x );
146 if( root ==
nullptr )
149 compareAndLink( root, newNode );
158 template <
class T,
class TCompare>
159 const T & PairingHeap<T,TCompare>::findMin( )
const 163 return root->element;
169 template <
class T,
class TCompare>
170 void PairingHeap<T,TCompare>::deleteMin( )
175 PairNode<T> *oldRoot = root;
177 if( root->leftChild ==
nullptr )
180 root = combineSiblings( root->leftChild );
181 COLA_ASSERT(counter);
189 template <
class T,
class TCompare>
190 const PairingHeap<T,TCompare> &
191 PairingHeap<T,TCompare>::operator=(
const PairingHeap<T,TCompare> & rhs )
196 root = clone( rhs.root );
197 counter = rhs.size();
207 template <
class T,
class TCompare>
208 void PairingHeap<T,TCompare>::reclaimMemory( PairNode<T> * t )
const 212 reclaimMemory( t->leftChild );
213 reclaimMemory( t->nextSibling );
225 template <
class T,
class TCompare>
226 void PairingHeap<T,TCompare>::decreaseKey( PairNode<T> *p,
229 COLA_ASSERT(!lessThan(p->element,newVal));
233 if( p->nextSibling !=
nullptr )
234 p->nextSibling->prev = p->prev;
235 if( p->prev->leftChild == p )
236 p->prev->leftChild = p->nextSibling;
238 p->prev->nextSibling = p->nextSibling;
240 p->nextSibling =
nullptr;
241 compareAndLink( root, p );
248 template <
class T,
class TCompare>
249 void PairingHeap<T,TCompare>::merge( PairingHeap<T,TCompare> *rhs )
252 PairNode<T> *broot=rhs->removeRootForMerge(rhsSize);
253 if (root ==
nullptr) {
256 compareAndLink(root, broot);
269 template <
class T,
class TCompare>
270 void PairingHeap<T,TCompare>::
271 compareAndLink( PairNode<T> * & first,
272 PairNode<T> *second )
const 274 if( second ==
nullptr )
277 if( lessThan(second->element,first->element) )
280 second->prev = first->prev;
281 first->prev = second;
282 first->nextSibling = second->leftChild;
283 if( first->nextSibling !=
nullptr )
284 first->nextSibling->prev = first;
285 second->leftChild = first;
291 second->prev = first;
292 first->nextSibling = second->nextSibling;
293 if( first->nextSibling !=
nullptr )
294 first->nextSibling->prev = first;
295 second->nextSibling = first->leftChild;
296 if( second->nextSibling !=
nullptr )
297 second->nextSibling->prev = second;
298 first->leftChild = second;
307 template <
class T,
class TCompare>
309 PairingHeap<T,TCompare>::combineSiblings( PairNode<T> *firstSibling )
311 if( firstSibling->nextSibling ==
nullptr )
316 for( ; firstSibling !=
nullptr; numSiblings++ )
318 if( numSiblings == (
int)siblingsTreeArray.size( ) )
319 siblingsTreeArray.resize( numSiblings * 2 );
320 siblingsTreeArray[ numSiblings ] = firstSibling;
321 firstSibling->prev->nextSibling =
nullptr;
322 firstSibling = firstSibling->nextSibling;
324 if( numSiblings == (
int)siblingsTreeArray.size( ) )
325 siblingsTreeArray.resize( numSiblings + 1 );
326 siblingsTreeArray[ numSiblings ] =
nullptr;
330 for( ; i + 1 < numSiblings; i += 2 )
331 compareAndLink( siblingsTreeArray[ i ], siblingsTreeArray[ i + 1 ] );
337 if( j == numSiblings - 3 )
338 compareAndLink( siblingsTreeArray[ j ], siblingsTreeArray[ j + 2 ] );
342 for( ; j >= 2; j -= 2 )
343 compareAndLink( siblingsTreeArray[ j - 2 ], siblingsTreeArray[ j ] );
344 return siblingsTreeArray[ 0 ];
351 template <
class T,
class TCompare>
353 PairingHeap<T,TCompare>::clone( PairNode<T> * t )
const 359 PairNode<T> *p =
new PairNode<T>( t->element );
360 if( ( p->leftChild = clone( t->leftChild ) ) != nullptr )
361 p->leftChild->prev = p;
362 if( ( p->nextSibling = clone( t->nextSibling ) ) != nullptr )
363 p->nextSibling->prev = p;
368 template <
class T,
class TCompare>
369 std::ostream& operator <<(std::ostream &os, const PairingHeap<T,TCompare> &b)
372 if (b.root !=
nullptr) {
373 PairNode<T> *r = b.root;
374 std::list<PairNode<T>*> q;
379 if (r->leftChild !=
nullptr) {
380 os << *r->element <<
">";
381 PairNode<T> *c = r->leftChild;
382 while (c !=
nullptr) {
384 os <<
"," << *c->element;