1 /**
2 * \brief Pairing heap datastructure implementation
3 *
4 * Based on example code in "Data structures and Algorithm Analysis in C++"
5 * by Mark Allen Weiss, used and released under the LGPL by permission
6 * of the author.
7 *
8 * No promises about correctness. Use at your own risk!
9 *
10 * Authors:
11 * Mark Allen Weiss
12 * Tim Dwyer <tgdwyer@gmail.com>
13 *
14 * Copyright (C) 2005 Authors
15 *
16 * Released under GNU LGPL. Read the file 'COPYING' for more information.
17 */
19 #include <vector>
20 #include <list>
21 #include "dsexceptions.h"
22 #include "PairingHeap.h"
24 #ifndef PAIRING_HEAP_CPP
25 #define PAIRING_HEAP_CPP
26 using namespace std;
27 /**
28 * Construct the pairing heap.
29 */
30 template <class T>
31 PairingHeap<T>::PairingHeap( bool (*lessThan)(T const &lhs, T const &rhs) )
32 {
33 root = NULL;
34 counter=0;
35 this->lessThan=lessThan;
36 }
39 /**
40 * Copy constructor
41 */
42 template <class T>
43 PairingHeap<T>::PairingHeap( const PairingHeap<T> & rhs )
44 {
45 root = NULL;
46 counter=rhs->size();
47 *this = rhs;
48 }
50 /**
51 * Destroy the leftist heap.
52 */
53 template <class T>
54 PairingHeap<T>::~PairingHeap( )
55 {
56 makeEmpty( );
57 }
59 /**
60 * Insert item x into the priority queue, maintaining heap order.
61 * Return a pointer to the node containing the new item.
62 */
63 template <class T>
64 PairNode<T> *
65 PairingHeap<T>::insert( const T & x )
66 {
67 PairNode<T> *newNode = new PairNode<T>( x );
69 if( root == NULL )
70 root = newNode;
71 else
72 compareAndLink( root, newNode );
73 counter++;
74 return newNode;
75 }
76 template <class T>
77 int PairingHeap<T>::size() {
78 return counter;
79 }
80 /**
81 * Find the smallest item in the priority queue.
82 * Return the smallest item, or throw Underflow if empty.
83 */
84 template <class T>
85 const T & PairingHeap<T>::findMin( ) const
86 {
87 if( isEmpty( ) )
88 throw Underflow( );
89 return root->element;
90 }
91 /**
92 * Remove the smallest item from the priority queue.
93 * Throws Underflow if empty.
94 */
95 template <class T>
96 void PairingHeap<T>::deleteMin( )
97 {
98 if( isEmpty( ) )
99 throw Underflow( );
101 PairNode<T> *oldRoot = root;
103 if( root->leftChild == NULL )
104 root = NULL;
105 else
106 root = combineSiblings( root->leftChild );
107 counter--;
108 delete oldRoot;
109 }
111 /**
112 * Test if the priority queue is logically empty.
113 * Returns true if empty, false otherwise.
114 */
115 template <class T>
116 bool PairingHeap<T>::isEmpty( ) const
117 {
118 return root == NULL;
119 }
121 /**
122 * Test if the priority queue is logically full.
123 * Returns false in this implementation.
124 */
125 template <class T>
126 bool PairingHeap<T>::isFull( ) const
127 {
128 return false;
129 }
131 /**
132 * Make the priority queue logically empty.
133 */
134 template <class T>
135 void PairingHeap<T>::makeEmpty( )
136 {
137 reclaimMemory( root );
138 root = NULL;
139 }
141 /**
142 * Deep copy.
143 */
144 template <class T>
145 const PairingHeap<T> &
146 PairingHeap<T>::operator=( const PairingHeap<T> & rhs )
147 {
148 if( this != &rhs )
149 {
150 makeEmpty( );
151 root = clone( rhs.root );
152 }
154 return *this;
155 }
157 /**
158 * Internal method to make the tree empty.
159 * WARNING: This is prone to running out of stack space.
160 */
161 template <class T>
162 void PairingHeap<T>::reclaimMemory( PairNode<T> * t ) const
163 {
164 if( t != NULL )
165 {
166 reclaimMemory( t->leftChild );
167 reclaimMemory( t->nextSibling );
168 delete t;
169 }
170 }
172 /**
173 * Change the value of the item stored in the pairing heap.
174 * Does nothing if newVal is larger than currently stored value.
175 * p points to a node returned by insert.
176 * newVal is the new value, which must be smaller
177 * than the currently stored value.
178 */
179 template <class T>
180 void PairingHeap<T>::decreaseKey( PairNode<T> *p,
181 const T & newVal )
182 {
183 if( lessThan(p->element,newVal) )
184 return; // newVal cannot be bigger
185 p->element = newVal;
186 if( p != root )
187 {
188 if( p->nextSibling != NULL )
189 p->nextSibling->prev = p->prev;
190 if( p->prev->leftChild == p )
191 p->prev->leftChild = p->nextSibling;
192 else
193 p->prev->nextSibling = p->nextSibling;
195 p->nextSibling = NULL;
196 compareAndLink( root, p );
197 }
198 }
200 /**
201 * Internal method that is the basic operation to maintain order.
202 * Links first and second together to satisfy heap order.
203 * first is root of tree 1, which may not be NULL.
204 * first->nextSibling MUST be NULL on entry.
205 * second is root of tree 2, which may be NULL.
206 * first becomes the result of the tree merge.
207 */
208 template <class T>
209 void PairingHeap<T>::
210 compareAndLink( PairNode<T> * & first,
211 PairNode<T> *second ) const
212 {
213 if( second == NULL )
214 return;
215 if( lessThan(second->element,first->element) )
216 {
217 // Attach first as leftmost child of second
218 second->prev = first->prev;
219 first->prev = second;
220 first->nextSibling = second->leftChild;
221 if( first->nextSibling != NULL )
222 first->nextSibling->prev = first;
223 second->leftChild = first;
224 first = second;
225 }
226 else
227 {
228 // Attach second as leftmost child of first
229 second->prev = first;
230 first->nextSibling = second->nextSibling;
231 if( first->nextSibling != NULL )
232 first->nextSibling->prev = first;
233 second->nextSibling = first->leftChild;
234 if( second->nextSibling != NULL )
235 second->nextSibling->prev = second;
236 first->leftChild = second;
237 }
238 }
240 /**
241 * Internal method that implements two-pass merging.
242 * firstSibling the root of the conglomerate;
243 * assumed not NULL.
244 */
245 template <class T>
246 PairNode<T> *
247 PairingHeap<T>::combineSiblings( PairNode<T> *firstSibling ) const
248 {
249 if( firstSibling->nextSibling == NULL )
250 return firstSibling;
252 // Allocate the array
253 static vector<PairNode<T> *> treeArray( 5 );
255 // Store the subtrees in an array
256 int numSiblings = 0;
257 for( ; firstSibling != NULL; numSiblings++ )
258 {
259 if( numSiblings == (int)treeArray.size( ) )
260 treeArray.resize( numSiblings * 2 );
261 treeArray[ numSiblings ] = firstSibling;
262 firstSibling->prev->nextSibling = NULL; // break links
263 firstSibling = firstSibling->nextSibling;
264 }
265 if( numSiblings == (int)treeArray.size( ) )
266 treeArray.resize( numSiblings + 1 );
267 treeArray[ numSiblings ] = NULL;
269 // Combine subtrees two at a time, going left to right
270 int i = 0;
271 for( ; i + 1 < numSiblings; i += 2 )
272 compareAndLink( treeArray[ i ], treeArray[ i + 1 ] );
274 int j = i - 2;
276 // j has the result of last compareAndLink.
277 // If an odd number of trees, get the last one.
278 if( j == numSiblings - 3 )
279 compareAndLink( treeArray[ j ], treeArray[ j + 2 ] );
281 // Now go right to left, merging last tree with
282 // next to last. The result becomes the new last.
283 for( ; j >= 2; j -= 2 )
284 compareAndLink( treeArray[ j - 2 ], treeArray[ j ] );
285 return treeArray[ 0 ];
286 }
288 /**
289 * Internal method to clone subtree.
290 * WARNING: This is prone to running out of stack space.
291 */
292 template <class T>
293 PairNode<T> *
294 PairingHeap<T>::clone( PairNode<T> * t ) const
295 {
296 if( t == NULL )
297 return NULL;
298 else
299 {
300 PairNode<T> *p = new PairNode<T>( t->element );
301 if( ( p->leftChild = clone( t->leftChild ) ) != NULL )
302 p->leftChild->prev = p;
303 if( ( p->nextSibling = clone( t->nextSibling ) ) != NULL )
304 p->nextSibling->prev = p;
305 return p;
306 }
307 }
308 template <class T>
309 ostream& operator <<(ostream &os, const PairingHeap<T> &b)
310 {
311 os<<"Heap:";
312 if (b.root != NULL) {
313 PairNode<T> *r = b.root;
314 list<PairNode<T>*> q;
315 q.push_back(r);
316 while (!q.empty()) {
317 r = q.front();
318 q.pop_front();
319 if (r->leftChild != NULL) {
320 os << *r->element << ">";
321 PairNode<T> *c = r->leftChild;
322 while (c != NULL) {
323 q.push_back(c);
324 os << "," << *c->element;
325 c = c->nextSibling;
326 }
327 os << "|";
328 }
329 }
330 }
331 return os;
332 }
333 #endif