Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

abacus::AbaPrioQueue< Type, Key > Class Template Reference

Bounded priority queues. More...

#include <ogdf/lib/abacus/bprioqueue.h>

+ Inheritance diagram for abacus::AbaPrioQueue< Type, Key >:

Public Member Functions

 AbaPrioQueue (int size)
 The constructor of an empty priority queue. More...
 
void clear ()
 Makes the priority queue empty. More...
 
int extractMin (Type &min)
 Retrieves and removes the minimal element from the priority queue. More...
 
int getMin (Type &min) const
 Retrieves the element with minimal key from the priority queue. More...
 
int getMinKey (Key &minKey) const
 Retrieves the key of the minimal element in the priority queue. More...
 
void insert (Type elem, Key key)
 Inserts an element in the priority queue. More...
 
int number () const
 Returns the number of elements stored in the priority queue. More...
 
void realloc (int newSize)
 Increases the size of the priority queue. More...
 
int size () const
 Returns the maximal number of elements which can be stored in the priority queue. More...
 
- Public Member Functions inherited from abacus::AbacusRoot
virtual ~AbacusRoot ()
 The destructor. More...
 

Private Attributes

AbaBHeap< Type, Key > heap_
 The heap implementing the priority queue. More...
 

Additional Inherited Members

- Static Public Member Functions inherited from abacus::AbacusRoot
static bool ascii2bool (const string &str)
 Converts the string str to a boolean value. More...
 
static bool endsWith (const string &str, const string &end)
 Returns true if str ends with end, false otherwise. More...
 
static double fracPart (double x)
 Returns the absolute value of the fractional part of x. More...
 
static const char * onOff (bool value)
 Converts a boolean variable to the strings "on" and "off". More...
 

Detailed Description

template<class Type, class Key>
class abacus::AbaPrioQueue< Type, Key >

Bounded priority queues.

A priority queue is a data structure storing a set of elements. Each element has a key which must be an ordered data type. The most important operations are the insertion of an element, the determination of the element having the minimal key, and the deletion of the element having minimal key.

Since the priority queue is implemented by a heap (class AbaBHeap) the insertion of a new element and the deletion of the minimal element require O(log n) time if n elements are stored in the priority queue. The element having minimal key can be determined in constant time.

To provide an efficient implementation the priority queue is bounded, i.e., the maximal number of elements is an argument of the constructor. However, if required, later a reallocation can be performed.

Definition at line 57 of file bprioqueue.h.

Constructor & Destructor Documentation

◆ AbaPrioQueue()

template<class Type , class Key >
abacus::AbaPrioQueue< Type, Key >::AbaPrioQueue ( int  size)

The constructor of an empty priority queue.

Parameters
sizeThe maximal number of elements the priority queue can hold without reallocation.

Member Function Documentation

◆ clear()

template<class Type , class Key >
void abacus::AbaPrioQueue< Type, Key >::clear ( )

Makes the priority queue empty.

◆ extractMin()

template<class Type , class Key >
int abacus::AbaPrioQueue< Type, Key >::extractMin ( Type &  min)

Retrieves and removes the minimal element from the priority queue.

Returns
0 If the priority queue is non-empty, 1 otherwise.
Parameters
minIf the priority queue is non-empty the minimal element is assigned to min.

◆ getMin()

template<class Type , class Key >
int abacus::AbaPrioQueue< Type, Key >::getMin ( Type &  min) const

Retrieves the element with minimal key from the priority queue.

Parameters
minIf the priority queue is non-empty the minimal element is assigned to min.
Returns
0 If the priority queue is non-empty, 1 otherwise.

◆ getMinKey()

template<class Type , class Key >
int abacus::AbaPrioQueue< Type, Key >::getMinKey ( Key &  minKey) const

Retrieves the key of the minimal element in the priority queue.

Parameters
minKeyHolds after the call the key of the minimal element in the priority queue, if the queue is non-emtpy.
Returns
0 If the priority queue is non-empty, 1 otherwise.

◆ insert()

template<class Type , class Key >
void abacus::AbaPrioQueue< Type, Key >::insert ( Type  elem,
Key  key 
)

Inserts an element in the priority queue.

Parameters
elemThe element being inserted.
keyThe key of the element.

◆ number()

template<class Type , class Key >
int abacus::AbaPrioQueue< Type, Key >::number ( ) const

Returns the number of elements stored in the priority queue.

◆ realloc()

template<class Type , class Key >
void abacus::AbaPrioQueue< Type, Key >::realloc ( int  newSize)

Increases the size of the priority queue.

It is not allowed to decrease the size of the priority queue. In this case an error message is output and the program stops.

Parameters
newSizeThe new size of the priority queue.

◆ size()

template<class Type , class Key >
int abacus::AbaPrioQueue< Type, Key >::size ( ) const

Returns the maximal number of elements which can be stored in the priority queue.

Member Data Documentation

◆ heap_

template<class Type , class Key >
AbaBHeap<Type, Key> abacus::AbaPrioQueue< Type, Key >::heap_
private

The heap implementing the priority queue.

Definition at line 122 of file bprioqueue.h.


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