Detailed Description
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 59 of file struct_gcgpqueue.h.
priority queue data structure More...
#include <struct_gcgpqueue.h>
Public Member Functions | |
SCIP_DECL_SORTPTRCOMP ((*ptrcomp)) | |
Data Fields | |
SCIP * | scip |
void ** | slots |
int | len |
int | size |
Member Function Documentation
◆ SCIP_DECL_SORTPTRCOMP()
GCG_PQueue::SCIP_DECL_SORTPTRCOMP | ( | * | ptrcomp | ) |
compares two data elements
Field Documentation
◆ scip
SCIP* GCG_PQueue::scip |
◆ slots
void** GCG_PQueue::slots |
array of element slots
Definition at line 63 of file struct_gcgpqueue.h.
Referenced by GCGpqueueDelete(), GCGpqueueElems(), GCGpqueueFirst(), GCGpqueueInsert(), GCGpqueueRemove(), pqueueHeapify(), and pqueueResize().
◆ len
int GCG_PQueue::len |
number of used element slots
Definition at line 64 of file struct_gcgpqueue.h.
Referenced by GCGpqueueClear(), GCGpqueueDelete(), GCGpqueueElems(), GCGpqueueFirst(), GCGpqueueInsert(), GCGpqueueNElems(), GCGpqueueRemove(), GCGpqueueResort(), and pqueueHeapify().
◆ size
int GCG_PQueue::size |
total number of available element slots
Definition at line 65 of file struct_gcgpqueue.h.
Referenced by pqueueResize().