# OpenGraph DrawingFramework

v.2012.07

BinaryHeap.h
Go to the documentation of this file.
1 /*
2  * $Revision: 2524$
3  *
4  * last checkin:
5  * $Author: gutwenger$
6  * $Date: 2012-07-03 09:54:22 +0200 (Tue, 03 Jul 2012)$
7  ***************************************************************/
8
44 #ifdef _MSC_VER
45 #pragma once
46 #endif
47
48 #ifndef OGDF_BINARY_HEAP_H
49 #define OGDF_BINARY_HEAP_H
50
51 #include<ogdf/basic/Array.h>
52
53 namespace ogdf {
54
55
56
57 // using min heaps
58 template <class X, class Priority=double, class INDEX=int>
60
61 public:
62
63  class Element {
64
65  friend class BinaryHeap<X, Priority, INDEX>;
66
67  private:
68  Priority priority;
69  X elem;
70  INDEX backIdx ; // the position in element array
71
72  // empty constructor
73  Element() { }
74
75  // construct element with object and priority
76  Element(X x, Priority prior) : priority(prior), elem(x) { }
77
78  //copy constructor
79  Element(const Element &origElem): priority(origElem.priority), elem(origElem.elem), backIdx(origElem.backIdx) { }
80
81  public:
82
83  //return the priority
84  Priority getPriority() const { return priority; }
85
86  // return reference to elem
87  const X &getElement() const { return elem; }
88
89  // return the position of this element in the heap array
90  INDEX getPos() const { return backIdx; }
91  };
92
93
95  BinaryHeap(INDEX c) : data(1, c, 0), s(0) { }
96
99  for (INDEX i = 1; i <= s; ++i) {
100  delete data[i];
101  data[i] = 0;
102  }
103  }
104
106  bool empty() const { return s == 0; }
107
109  INDEX size() const { return s; }
110
111
112
114  void decPriority(const Element &elem, // handle to the element
115  Priority prior // new priority, must be smaller then the old value
116  ) {
117  INDEX i = elem.backIdx;
118
119  OGDF_ASSERT(i <= s);
120
121  if (data[i]->getPriority() < prior)
122  throw "New key is greater than current key.";
123
124  data[i]->priority = prior;
125  while (i > 1 && (data[getParent(i)]->getPriority() > data[i]->getPriority()) ) {
126  swap(i, getParent(i));
127  i = getParent(i);
128  }
129  }
130
132  const Element & insert(X obj, Priority prior) {
133  Element *h_elem = new Element (obj, prior);
134  ++s;
135  if (s == capacity())
136  data.grow(capacity(), 0); // double the size
137  h_elem->backIdx = s; // store the position
138  data[s] = h_elem;
139  INDEX i = s;
140  while ( (i > 1) && ( data[getParent(i)]->getPriority() > data[i]->getPriority()) ) {
141  swap(i, getParent(i));
142  i = getParent(i);
143  }
144  return *h_elem;
145  }
146
148  const Element & push(X obj, Priority prior) {
149  return insert(obj, prior);
150  }
151
153  const X & getMin() const {
154  return data[1]->getElement();
155  }
156
158  const X & top() const {
159  return getMin();
160  }
161
164  if (empty())
165  throw "Heap underflow error!";
166
167  Element copy = *data[1];
168  Element *p = data[1];
169  swap(1, s);
170  --s;
171  delete p;
172  minHeapify(1);
173  data[s+1] = 0;
174  return copy.getElement();
175  }
176
178  X pop() {
179  return extractMin();
180  }
181
183  void clear() {
184  for (INDEX i = 1; i <= s; ++i) {
185  delete data[i];
186  data[i] = 0;
187  }
188  s = 0;
189  }
190
192  const X & operator[](INDEX idx) const {
193  return data[idx+1]->getElement();
194  }
195
196
197  private :
198
199  Array<Element *, INDEX> data; // heap array starts at index 1
200  INDEX s; // current number of elements
201
203  INDEX capacity() const { return data.size(); }
204
205  void swap(INDEX pos1, INDEX pos2) {
206  Element *tmp = data[pos1];
207  data[pos1] = data[pos2];
208  data[pos2] = tmp;
209  // update the position
210  data[pos2]->backIdx = pos2;
211  data[pos1]->backIdx = pos1;
212  }
213
214
215
216  void minHeapify(INDEX pos) {
217  INDEX l = getLeft(pos);
218  INDEX r = getRight(pos);
219  INDEX smallest;
220  if (l <= size() && data[l]->getPriority() < data[pos]->getPriority() )
221  smallest = l;
222  else
223  smallest = pos;
224  if (r <= size() && data[r]->getPriority() < data[smallest]->getPriority())
225  smallest = r;
226  if (smallest != pos) {
227  swap(pos, smallest);
228  minHeapify(smallest);
229  }
230  }
231
232
233  INDEX getParent(INDEX pos) const {return pos/2;}
234
235  INDEX getLeft(INDEX pos) const {return pos*2;}
236
237  INDEX getRight(INDEX pos) const {return pos*2+1;}
238
239 };
240
241 }//namespace ogdf
242
243 #endif