Open
Graph Drawing
Framework

 v.2010.10
 

BinaryHeap.h

Go to the documentation of this file.
00001 /*
00002  * $Revision: 2013 $
00003  * 
00004  * last checkin:
00005  *   $Author: gutwenger $ 
00006  *   $Date: 2010-08-27 14:56:33 +0200 (Fri, 27 Aug 2010) $ 
00007  ***************************************************************/
00008  
00051 #ifdef _MSC_VER
00052 #pragma once
00053 #endif
00054 
00055 #ifndef OGDF_BINARY_HEAP_H
00056 #define OGDF_BINARY_HEAP_H
00057 
00058 #include<ogdf/basic/Array.h>
00059 
00060 namespace ogdf {
00061 
00062     
00063 
00064 // using min heaps 
00065 template <class X, class Priority=double, class INDEX=int>
00066 class OGDF_EXPORT BinaryHeap {
00067     
00068 public:
00069 
00070     class Element {
00071 
00072         friend class BinaryHeap<X, Priority, INDEX>;
00073 
00074         private:    
00075             Priority priority;
00076             X elem;
00077             INDEX backIdx ; // the position in element array
00078 
00079             // empty constructor
00080             Element() { }
00081             
00082             // construct element with object and priority
00083             Element(X x, Priority prior) : priority(prior), elem(x) { }
00084 
00085             //copy constructor
00086             Element(const Element &origElem): priority(origElem.priority), elem(origElem.elem), backIdx(origElem.backIdx) { }               
00087 
00088         public: 
00089                 
00090             //return the priority
00091             Priority getPriority() const { return priority; }
00092                 
00093             // return reference to elem
00094             const X &getElement() const { return elem; }            
00095 
00096             // return the position of this element in the heap array
00097             INDEX getPos() const { return backIdx; }
00098     };
00099 
00100     
00102     BinaryHeap(INDEX c) : data(1, c, 0), s(0) { }
00103 
00105     ~BinaryHeap() {
00106         for (INDEX i = 1; i <= s; ++i) {            
00107             delete data[i];
00108             data[i] = 0;
00109         }       
00110     }
00111 
00113     bool empty() const { return s == 0; }
00114     
00116     INDEX size() const { return s; }    
00117     
00118     
00119     
00121     void decPriority(const Element &elem, // handle to the element
00122                             Priority prior // new priority, must be smaller then the old value
00123                             ) {
00124         INDEX i = elem.backIdx;
00125 
00126         OGDF_ASSERT(i <= s);
00127 
00128         if (data[i]->getPriority() < prior)
00129             throw "New key is greater than current key.";
00130         
00131         data[i]->priority = prior; 
00132         while (i > 1 && (data[getParent(i)]->getPriority() > data[i]->getPriority()) ) {
00133             swap(i, getParent(i));
00134             i = getParent(i);
00135         }       
00136     }
00137 
00139     const Element & insert(X obj, Priority prior) {     
00140         Element *h_elem = new Element (obj, prior); 
00141         ++s;        
00142         if (s == capacity())
00143             data.grow(capacity(), 0); // double the size
00144         h_elem->backIdx = s; // store the position      
00145         data[s] = h_elem;       
00146         INDEX i = s;
00147         while ( (i > 1) && ( data[getParent(i)]->getPriority() > data[i]->getPriority()) ) {
00148             swap(i, getParent(i));
00149             i = getParent(i);
00150         }       
00151         return *h_elem;
00152     }   
00153 
00155     const Element & push(X obj, Priority prior) {
00156         return insert(obj, prior);
00157     }
00158 
00160     const X & getMin() const {              
00161         return data[1]->getElement();
00162     } 
00163 
00165     const X & top() const {
00166         return getMin();
00167     }
00168 
00170     X extractMin() {
00171         if (empty())
00172             throw "Heap underflow error!";  
00173 
00174         Element copy = *data[1];    
00175         Element *p = data[1];
00176         swap(1, s);     
00177         --s;
00178         delete p;
00179         minHeapify(1);      
00180         data[s+1] = 0;
00181         return copy.getElement();
00182     }
00183         
00185     X pop() {
00186         return extractMin();
00187     }
00188 
00190     void clear() {
00191         for (INDEX i = 1; i <= s; ++i) {            
00192             delete data[i];
00193             data[i] = 0;
00194         }
00195         s = 0;
00196     }
00197 
00199     const X & operator[](INDEX idx) const {
00200         return data[idx+1]->getElement();
00201     }
00202 
00203 
00204     private :
00205 
00206     Array<Element *, INDEX> data; // heap array starts at index 1               
00207     INDEX s; // current number of elements 
00208     
00210     INDEX capacity() const { return data.size(); }
00211     
00212     void swap(INDEX pos1, INDEX pos2) {
00213         Element *tmp = data[pos1];
00214         data[pos1] = data[pos2];
00215         data[pos2] = tmp;
00216         // update the position
00217         data[pos2]->backIdx = pos2;
00218         data[pos1]->backIdx = pos1;
00219     } 
00220     
00221 
00222     
00223     void minHeapify(INDEX pos) {
00224         INDEX l = getLeft(pos);
00225         INDEX r = getRight(pos);
00226         INDEX smallest;
00227         if (l <= size() && data[l]->getPriority() < data[pos]->getPriority() )
00228             smallest = l;
00229         else
00230             smallest = pos;
00231         if (r <= size() && data[r]->getPriority() < data[smallest]->getPriority())
00232             smallest = r;
00233         if (smallest != pos) {
00234             swap(pos, smallest);
00235             minHeapify(smallest);
00236         } 
00237     }
00238     
00239 
00240     INDEX getParent(INDEX pos) const {return pos/2;}
00241 
00242     INDEX getLeft(INDEX pos) const {return pos*2;}
00243 
00244     INDEX getRight(INDEX pos) const {return pos*2+1;}   
00245 
00246 };
00247 
00248 }//namespace ogdf
00249 
00250 #endif