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

memory growing factor

Definition at line 80 of file struct_misc.h.

Referenced by pqueueResize().

◆ 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.