Scippy

SCIP

Solving Constraint Integer Programs

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

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