SCIP
Solving Constraint Integer Programs
Solving Constraint Integer Programs
priority queue data structure Elements are stored in an array, which grows dynamically in size as new elements are added to the queue. The ordering is done through a pointer comparison function. The array is organized as follows. The root element (that is the "best" element $r$ with $r <= x$ for all $x$) is stored in position 0. The children of an element at position $p$ are stored at positions $q_1 = 2*p+1$ and $q_2 = 2*p+2$. That means, the parent of the element at position $q$ is at position $p = (q-1)/2$. At any time, the condition holds that $p <= q$ for each parent $p$ and its children $q$. Insertion and removal of single elements needs time $O(log n)$.
Definition at line 64 of file struct_misc.h.
#include <struct_misc.h>
Public Member Functions | |
| SCIP_DECL_SORTPTRCOMP ((*ptrcomp)) | |
Data Fields | |
| SCIP_Real | sizefac |
| void ** | slots |
| int | len |
| int | size |
| SCIP_PQueue::SCIP_DECL_SORTPTRCOMP | ( | * | ptrcomp | ) |
compares two data elements
| SCIP_Real SCIP_PQueue::sizefac |
| void** SCIP_PQueue::slots |
array of element slots
Definition at line 68 of file struct_misc.h.
Referenced by pqueueResize(), SCIPpqueueElems(), SCIPpqueueFirst(), SCIPpqueueInsert(), and SCIPpqueueRemove().
| int SCIP_PQueue::len |
number of used element slots
Definition at line 69 of file struct_misc.h.
Referenced by SCIPpqueueClear(), SCIPpqueueElems(), SCIPpqueueFirst(), SCIPpqueueInsert(), SCIPpqueueNElems(), and SCIPpqueueRemove().
| int SCIP_PQueue::size |
total number of available element slots
Definition at line 70 of file struct_misc.h.
Referenced by pqueueResize().