40 return mHeap[0].mIndex;
77 PQNode heap_node(index, key);
78 mHeap.push_back(heap_node);
82 while ((pos > 0) && (
mHeap[
parent(pos)].mKey > key))
96 for (i = 0; i < numberOfReactions; i++)
113 if (static_cast<unsigned int>(index) !=
mHeap.size())
119 PQNode heap_node(index, key);
120 mHeap.push_back(heap_node);
122 size_t position = index;
142 mHeap[pos].mKey = new_key;
151 size_t index1 =
mHeap[pos1].mIndex;
152 size_t index2 =
mHeap[pos2].mIndex;
154 mHeap[pos1].mIndex = index2;
157 mHeap[pos2].mIndex = index1;
158 mHeap[pos2].mKey = tempkey;
168 size_t highest_priority = current;
171 if ((static_cast<unsigned int>(left) <
mHeap.size()) && (
mHeap[left].mKey <
mHeap[current].mKey))
173 highest_priority = left;
176 if ((static_cast<unsigned int>(right) <
mHeap.size()) && (
mHeap[right].mKey <
mHeap[highest_priority].mKey))
178 highest_priority = right;
181 if (highest_priority != current)
190 size_t parent_pos =
parent(pos);
194 keyval <
mHeap[parent_pos].mKey)
206 if (left <
mHeap.size())
208 min =
mHeap[left].mKey;
214 if ((right <
mHeap.size()) && ((val =
mHeap[right].mKey) <
min))
220 if ((min_pos > 0) && (keyval >
min))
229 #ifdef TEST_PRIORITY_QUEUE
231 int main(
int argc,
char **argv)
236 cout <<
"Usage: " << argv[0] <<
" <number of pairs to generate>" << endl;
240 int count = atoi(argv[1]);
241 cout <<
"Creating priority queue of size " << count << endl;
242 std::vector<C_FLOAT64> invec;
246 cout <<
"Input vector:\n";
248 for (
int i = 0; i < count; i++)
250 rndval = rand->getUniformRandom();
251 invec.push_back(rndval);
252 cout <<
"element " << i <<
":" << rndval << endl;
256 cout <<
"Building heap\n";
258 cout <<
"Done building heap\n";
260 cout <<
"\nPriority Queue:\n";
262 for (
int i = 0; i < count; i++)
266 for (
int j = 0; j < count; j++) cout <<
" " << j <<
"-" << pq[j];
269 cout <<
"Position: " << i;
270 cout <<
" Index = " << pq.
topIndex();
271 cout <<
" Key = " << pq.
topKey() << endl;
278 #endif // TEST_PRIORITY_QUEUE
282 os <<
"(" << d.
mIndex <<
", " << d.
mKey <<
")";
290 os <<
"PQ: " << std::endl;
292 std::vector <PQNode>::const_iterator it;
293 os <<
" mHeap: " << std::endl;
295 for (it = d.
mHeap.begin(); it != d.
mHeap.end(); it++)
296 os << *it << std::endl;
298 os <<
" mIndexPointer: " << std::endl;
std::vector< size_t > mIndexPointer
int main(int argc, char **argv)
std::vector< PQNode > mHeap
size_t leftChild(const size_t pos) const
std::ostream & operator<<(std::ostream &os, const PQNode &d)
size_t insertStochReaction(const size_t index, const C_FLOAT64 key)
void heapify(const size_t pos)
void updateAux(const size_t position)
size_t removeStochReaction(const size_t index)
void updateNode(const size_t index, const C_FLOAT64 key)
void swapNodes(const size_t index1, const size_t index2)
size_t rightChild(const size_t pos) const
size_t parent(const size_t pos) const
size_t pushPair(const size_t index, const C_FLOAT64 key)
void initializeIndexPointer(const size_t numberOfReactions)