All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Public Member Functions | List of all members
Aux::PrioQueueForInts Class Reference

Addressable priority queue for elements in the range [0,n) and integer priorities in the range [0, maxPrio]. More...

#include <PrioQueueForInts.h>

Public Member Functions

 PrioQueueForInts (std::vector< index > &prios, index maxPrio)
 Constructor that initializes the PQ with the full batch of entries. More...
 
 ~PrioQueueForInts ()=default
 Destructor. More...
 
void remove (index elem)
 Remove element with key key from PQ. More...
 
void changePrio (index elem, index prio)
 Changes priority of element elem to priority prio. More...
 
index extractMin ()
 
index extractMax ()
 
index extractAt (index prio)
 
index priority (index elem)
 
bool empty () const
 
count size () const
 

Detailed Description

Addressable priority queue for elements in the range [0,n) and integer priorities in the range [0, maxPrio].

Amortized constant running time for each operation.

Constructor & Destructor Documentation

Aux::PrioQueueForInts::PrioQueueForInts ( std::vector< index > &  prios,
index  maxPrio 
)

Constructor that initializes the PQ with the full batch of entries.

Parameters
[in]priosContains the batch of n entries, where prios[i] represents the key-value pair (i, prios[i]). Priorities must be in range [0, maxPrio] or none (the latter means that the element does not exist).
[in]maxPrioMaximum priority value.
Aux::PrioQueueForInts::~PrioQueueForInts ( )
default

Destructor.

Member Function Documentation

void Aux::PrioQueueForInts::changePrio ( index  elem,
index  prio 
)

Changes priority of element elem to priority prio.

Parameters
[in]elemElement whose priority is changed.
[in]prioNew priority, must be in range [0, maxPrio].
bool Aux::PrioQueueForInts::empty ( ) const
Returns
True if priority queue does not contain any elements, otherwise false.
index Aux::PrioQueueForInts::extractAt ( index  prio)
Returns
Arbitrary element with priority prio. Returns none if no such element exists.
Parameters
[in]Priorityfor which a corresponding element shall be returned, must be in range [0, maxPrio].
index Aux::PrioQueueForInts::extractMax ( )
Returns
Element with maximum priority.
index Aux::PrioQueueForInts::extractMin ( )
Returns
Element with minimum priority.
index Aux::PrioQueueForInts::priority ( index  elem)
Returns
Priority of elem elem.
Parameters
[in]Elementwhose priority shall be returned.
void Aux::PrioQueueForInts::remove ( index  elem)

Remove element with key key from PQ.

Parameters
[in]elemElement to be removed.
count Aux::PrioQueueForInts::size ( ) const
Returns
Number of elements contained in priority queue.

The documentation for this class was generated from the following files: