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

size	The 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

min	If 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

min	If 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

minKey

Holds 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

elem	The element being inserted.
key	The 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

newSize

The 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:

• include/ogdf/lib/abacus/bprioqueue.h