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 \leq 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 \leq q \) for each parent \( p \) and its children \( q \) . Insertion and removal of single elements needs time \( O(log n) \) .
Definition at line 78 of file struct_misc.h.
#include <struct_misc.h>
Public Member Functions | |
SCIP_DECL_SORTPTRCOMP ((*ptrcomp)) | |
SCIP_DECL_PQUEUEELEMCHGPOS ((*elemchgpos)) | |
Data Fields | |
SCIP_Real | sizefac |
void ** | slots |
int | len |
int | size |
Member Function Documentation
◆ SCIP_DECL_SORTPTRCOMP()
SCIP_PQueue::SCIP_DECL_SORTPTRCOMP | ( | * | ptrcomp | ) |
compares two data elements
◆ SCIP_DECL_PQUEUEELEMCHGPOS()
SCIP_PQueue::SCIP_DECL_PQUEUEELEMCHGPOS | ( | * | elemchgpos | ) |
callback to act on position change of elem in priority queue, or NULL
Field Documentation
◆ sizefac
SCIP_Real SCIP_PQueue::sizefac |
◆ slots
void** SCIP_PQueue::slots |
array of element slots
Definition at line 83 of file struct_misc.h.
Referenced by pqueueElemChgPos(), pqueueResize(), SCIPpqueueDelPos(), SCIPpqueueElems(), SCIPpqueueFind(), SCIPpqueueFirst(), SCIPpqueueInsert(), and SCIPpqueueRemove().
◆ len
int SCIP_PQueue::len |
number of used element slots
Definition at line 84 of file struct_misc.h.
Referenced by SCIPpqueueClear(), SCIPpqueueDelPos(), SCIPpqueueElems(), SCIPpqueueFirst(), SCIPpqueueInsert(), SCIPpqueueNElems(), and SCIPpqueueRemove().
◆ size
int SCIP_PQueue::size |
total number of available element slots
Definition at line 85 of file struct_misc.h.
Referenced by pqueueResize().