[next] [prev] [prev-tail] [tail] [up]

6.62 ABA_BHEAP< Type, Key > Class Template Reference

This template class implements a heap with a fixed maximal size, however a reallocation can be performed if required.

#include <bheap.h>

Inheritance diagram for ABA_BHEAP< Type, Key >::

PIC

Public Member Functions

Private Member Functions

Private Attributes

Friends

6.62.1 Detailed Description

template<class Type, class Key> class ABA_BHEAP< Type, Key >

This template class implements a heap with a fixed maximal size, however a reallocation can be performed if required.

Definition at line 74 of file bheap.h.

6.62.2 Constructor & Destructor Documentation

6.62.2.1 template<class Type, class Key> ABA_BHEAP< Type, Key >::ABA_BHEAP (ABA_GLOBAL * glob, int size)

A constructor.

Parameters:

glob
A pointer to the corresponding global object.
size
The maximal number of elements which can be stored.

6.62.2.2 template<class Type, class Key> ABA_BHEAP< Type, Key >::ABA_BHEAP (ABA_GLOBAL * glob, const ABA_BUFFER< Type > & elems, const ABA_BUFFER< Key > & keys)

A constructor with initialization.

The heap is initialized from an ABA_BUFFER of elements and a corresponding ABA_BUFFER of keys. The running time is O(n) for n elements.

Parameters:

glob
A pointer to the corresponding global object.
elem
A ABA_BUFFER wich contains the elements.
elem
A ABA_BUFFER wich contains the keys.

6.62.3 Member Function Documentation

6.62.3.1 template<class Type, class Key> void ABA_BHEAP< Type, Key >::insert (Type elem, Key key)

Inserts an item with a key into the heap.

It is a fatal error to perform this operation if the heap is full. If the precompiler flag -DABACUSSAFE is set, we check if the heap is not already full.

Parameters:

elem
The element being inserted into the heap.
key
The key of this element.

6.62.3.2 template<class Type, class Key> Type ABA_BHEAP< Type, Key >::getMin () const

Returns:

The minimum element of the heap. This operation must not be performed if the heap is empty. Since the heap property holds the element having minimal key is always stored in heap_[0].

6.62.3.3 template<class Type, class Key> Key ABA_BHEAP< Type, Key >::getMinKey () const

Returns:

The key of the minimum element of the heap. This operation must not be performed if the heap is empty. Since the heap property holds the element having minimal key is always stored in heap_[0] and its key in key_[0].

6.62.3.4 template<class Type, class Key> Type ABA_BHEAP< Type, Key >::extractMin ()

Accesses and removes the minimum element from the heap.

The minimum element is stored in the root of the tree, i.e., in heap_[0]. If the heap does not become empty by removing the minimal element, we move the last element stored in heap_ to the root (heap_[0]). Whereas this operation can destroy the heap property, the two subtrees rooted at nodes 1 and 2 still satisfy the heap property. Hence calling heapify(0) will restore the overall heap property.

Returns:

The minimum element of the heap.

6.62.3.5 template<class Type, class Key> void ABA_BHEAP< Type, Key >::clear ()

Empties the heap.

6.62.3.6 template<class Type, class Key> int ABA_BHEAP< Type, Key >::size () const

Returns:

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

6.62.3.7 template<class Type, class Key> int ABA_BHEAP< Type, Key >::number () const

Returns:

The number of elements in the heap.

6.62.3.8 template<class Type, class Key> bool ABA_BHEAP< Type, Key >::empty () const

Returns:

true If there are no elements in the heap,

false otherwise.

6.62.3.9 template<class Type, class Key> void ABA_BHEAP< Type, Key >::realloc (int newSize)

Changes the size of the heap.

Parameters:

newSize
The new maximal number of elements in the heap.

6.62.3.10 template<class Type, class Key> void ABA_BHEAP< Type, Key >::check () const

Stops with an error message if the heap properties are violated.

This function is used for debugging this class.

6.62.3.11 template<class Type, class Key> int ABA_BHEAP< Type, Key >::leftSon (int i) const [private]

Returns the index of the left son of node i.

6.62.3.12 template<class Type, class Key> int ABA_BHEAP< Type, Key >::rightSon (int i) const [private]

Returns the index of the right son of node i.

6.62.3.13 template<class Type, class Key> int ABA_BHEAP< Type, Key >::father (int i) const [private]

Returns the index of the father of element i.

6.62.3.14 template<class Type, class Key> void ABA_BHEAP< Type, Key >::heapify (int i) [private]

Is the central function to maintain the heap property.

The function assumes that the two trees rooted at left(i) and right(i) fulfil already the heap property and restores the heap property of the (sub-) tree rooted at i.

6.62.4 Friends And Related Function Documentation

6.62.4.1 template<class Type, class Key> ostream& operator<< (ostream & out, const ABA_BHEAP< Type, Key > & rhs) [friend]

The output operator writes the elements of the heap together with their keys on an output stream.

Returns:

A reference to the output stream.

Parameters:

out
The output stream.
rhs
The heap being output.

6.62.5 Member Data Documentation

6.62.5.1 template<class Type, class Key> ABA_GLOBAL*ABA_BHEAP< Type, Key >::glob_ [private]

Definition at line 216 of file bheap.h.

6.62.5.2 template<class Type, class Key> ABA_ARRAY<Type> ABA_BHEAP< Type, Key >::heap_ [private]

Definition at line 217 of file bheap.h.

6.62.5.3 template<class Type, class Key> ABA_ARRAY<Key> ABA_BHEAP< Type, Key >::keys_ [private]

Definition at line 218 of file bheap.h.

6.62.5.4 template<class Type, class Key> int ABA_BHEAP< Type, Key >::n_ [private]

Definition at line 219 of file bheap.h.

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

[next] [prev] [prev-tail] [front] [up]