SCIP_PQueue Struct Reference

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 63 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

Member Function Documentation

SCIP_PQueue::SCIP_DECL_SORTPTRCOMP

(

*

ptrcomp

)

compares two data elements

Field Documentation

SCIP_Real SCIP_PQueue::sizefac

memory growing factor

Definition at line 65 of file struct_misc.h.

Referenced by pqueueResize().

void** SCIP_PQueue::slots

array of element slots

Definition at line 67 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 68 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 69 of file struct_misc.h.

Referenced by pqueueResize().