48 #ifndef OGDF_BINARY_HEAP_H
49 #define OGDF_BINARY_HEAP_H
58 template <
class X,
class Priority=
double,
class INDEX=
int>
76 Element(X x, Priority prior) : priority(prior), elem(x) { }
79 Element(
const Element &origElem): priority(origElem.priority), elem(origElem.elem), backIdx(origElem.backIdx) { }
90 INDEX
getPos()
const {
return backIdx; }
99 for (INDEX i = 1; i <= s; ++i) {
106 bool empty()
const {
return s == 0; }
109 INDEX
size()
const {
return s; }
121 if (data[i]->getPriority() < prior)
122 throw "New key is greater than current key.";
124 data[i]->priority = prior;
125 while (i > 1 && (data[getParent(i)]->getPriority() > data[i]->getPriority()) ) {
126 swap(i, getParent(i));
136 data.grow(capacity(), 0);
140 while ( (i > 1) && ( data[getParent(i)]->getPriority() > data[i]->getPriority()) ) {
141 swap(i, getParent(i));
149 return insert(obj, prior);
154 return data[1]->getElement();
165 throw "Heap underflow error!";
184 for (INDEX i = 1; i <= s; ++i) {
193 return data[idx+1]->getElement();
205 void swap(INDEX pos1, INDEX pos2) {
207 data[pos1] = data[pos2];
211 data[pos1]->backIdx = pos1;
217 INDEX l = getLeft(pos);
218 INDEX r = getRight(pos);
220 if (l <= size() && data[l]->getPriority() < data[pos]->getPriority() )
224 if (r <= size() && data[r]->getPriority() < data[smallest]->getPriority())
226 if (smallest != pos) {
228 minHeapify(smallest);
235 INDEX
getLeft(INDEX pos)
const {
return pos*2;}