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 */
18 #ifndef PAIRING_HEAP_H_
19 #define PAIRING_HEAP_H_
20 #include <stdlib.h>
21 #include <fstream>
22 // Pairing heap class
23 //
24 // CONSTRUCTION: with no parameters
25 //
26 // ******************PUBLIC OPERATIONS*********************
27 // PairNode & insert( x ) --> Insert x
28 // deleteMin( minItem ) --> Remove (and optionally return) smallest item
29 // T findMin( ) --> Return smallest item
30 // bool isEmpty( ) --> Return true if empty; else false
31 // bool isFull( ) --> Return true if empty; else false
32 // void makeEmpty( ) --> Remove all items
33 // void decreaseKey( PairNode p, newVal )
34 // --> Decrease value in node p
35 // ******************ERRORS********************************
36 // Throws Underflow as warranted
39 // Node and forward declaration because g++ does
40 // not understand nested classes.
41 template <class T>
42 class PairingHeap;
44 template <class T>
45 std::ostream& operator<< (std::ostream &os,const PairingHeap<T> &b);
47 template <class T>
48 class PairNode
49 {
50 friend std::ostream& operator<< <T>(std::ostream &os,const PairingHeap<T> &b);
51 T element;
52 PairNode *leftChild;
53 PairNode *nextSibling;
54 PairNode *prev;
56 PairNode( const T & theElement ) :
57 element( theElement ),
58 leftChild(NULL), nextSibling(NULL), prev(NULL)
59 { }
60 friend class PairingHeap<T>;
61 };
63 template <class T>
64 class Comparator
65 {
66 public:
67 virtual bool isLessThan(T const &lhs, T const &rhs) const = 0;
68 };
70 template <class T>
71 class PairingHeap
72 {
73 friend std::ostream& operator<< <T>(std::ostream &os,const PairingHeap<T> &b);
74 public:
75 PairingHeap( bool (*lessThan)(T const &lhs, T const &rhs) );
76 PairingHeap( const PairingHeap & rhs );
77 virtual ~PairingHeap( );
79 bool isEmpty( ) const;
80 bool isFull( ) const;
81 int size();
83 PairNode<T> *insert( const T & x );
84 const T & findMin( ) const;
85 void deleteMin( );
86 const T extractMin( ) {
87 T v = findMin();
88 deleteMin();
89 return v;
90 }
91 void makeEmpty( );
92 void decreaseKey( PairNode<T> *p, const T & newVal );
93 void merge( PairingHeap<T> *rhs )
94 {
95 PairNode<T> *broot=rhs->getRoot();
96 if (root == NULL) {
97 if(broot != NULL) {
98 root = broot;
99 }
100 } else {
101 compareAndLink(root, broot);
102 }
103 counter+=rhs->size();
104 }
106 const PairingHeap & operator=( const PairingHeap & rhs );
107 protected:
108 PairNode<T> * getRoot() {
109 PairNode<T> *r=root;
110 root=NULL;
111 return r;
112 }
113 private:
114 PairNode<T> *root;
115 bool (*lessThan)(T const &lhs, T const &rhs);
116 int counter;
117 void reclaimMemory( PairNode<T> *t ) const;
118 void compareAndLink( PairNode<T> * & first, PairNode<T> *second ) const;
119 PairNode<T> * combineSiblings( PairNode<T> *firstSibling ) const;
120 PairNode<T> * clone( PairNode<T> * t ) const;
121 };
123 #include "PairingHeap.cpp"
124 #endif