6.63 ABA_BPRIOQUEUE< Type, Key > Class Template Reference

Since the priority queue is implemented by a heap (class ABA_BHEAP) 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.

#include <bprioqueue.h>

Inheritance diagram for ABA_BPRIOQUEUE< Type, Key >::

Public Member Functions

• ABA_BPRIOQUEUE (ABA_GLOBAL *glob, int size)
• void insert (Type elem, Key key)
• int getMin (Type &min) const
• int getMinKey (Key &minKey) const
• int extractMin (Type &min)

  Extends the function getMin(min) in the way that the minimal element is also removed from the priority queue.

• void clear ()
• int size () const
• int number () const
• void realloc (int newSize)

Private Attributes

• ABA_GLOBAL *glob_
• ABA_BHEAP< Type, Key > heap_

6.63.1 Detailed Description

template<class Type, class Key> class ABA_BPRIOQUEUE< Type, Key >

Since the priority queue is implemented by a heap (class ABA_BHEAP) 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.

Definition at line 57 of file bprioqueue.h.

6.63.2 Constructor & Destructor Documentation

6.63.2.1 template<class Type, class Key> ABA_BPRIOQUEUE< Type, Key >::ABA_BPRIOQUEUE (ABA_GLOBAL * glob, int size)

The constructor of an empty priority queue.

Parameters:

glob

A pointer to the corresponding object.

size

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

6.63.3 Member Function Documentation

6.63.3.1 template<class Type, class Key> void ABA_BPRIOQUEUE< 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.

6.63.3.2 template<class Type, class Key> int ABA_BPRIOQUEUE< Type, Key >::getMin (Type & min) const

Retrieves the element with minimal key 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.

6.63.3.3 template<class Type, class Key> int ABA_BPRIOQUEUE< Type, Key >::getMinKey (Key & minKey) const

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

Returns:

0 If the priority queue is non-empty,

1 otherwise.

Parameters:

minKey

Holds after the call the key of the minimal element in the priority queue, if the queue is non-emtpy.

6.63.3.4 template<class Type, class Key> int ABA_BPRIOQUEUE< Type, Key >::extractMin (Type & min)

Extends the function getMin(min) in the way that the minimal element is also removed 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.

6.63.3.5 template<class Type, class Key> void ABA_BPRIOQUEUE< Type, Key >::clear ()

Makes the priority queue empty.

6.63.3.6 template<class Type, class Key> int ABA_BPRIOQUEUE< Type, Key >::size () const

Returns:

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

6.63.3.7 template<class Type, class Key> int ABA_BPRIOQUEUE< Type, Key >::number () const

Returns:

The number of elements stored in the priority queue.

6.63.3.8 template<class Type, class Key> void ABA_BPRIOQUEUE< 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.

6.63.4 Member Data Documentation

6.63.4.1 template<class Type, class Key> ABA_GLOBAL*ABA_BPRIOQUEUE< Type, Key >::glob_ [private]

A pointer to the corresponding global object.

Definition at line 131 of file bprioqueue.h.

6.63.4.2 template<class Type, class Key> ABA_BHEAP<Type, Key> ABA_BPRIOQUEUE< Type, Key >::heap_ [private]

The heap implementing the priority queue.

Definition at line 135 of file bprioqueue.h.

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

• Include/abacus/bprioqueue.h