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. More...

#include <bheap.h>

Inheritance diagram for ABA_BHEAP< Type, Key >:

List of all members.

Public Member Functions
	ABA_BHEAP (ABA_GLOBAL *glob, int size)
	ABA_BHEAP (ABA_GLOBAL *glob, const ABA_BUFFER< Type > &elems, const ABA_BUFFER< Key > &keys)
void	insert (Type elem, Key key)
Type	getMin () const
Key	getMinKey () const
Type	extractMin ()
void	clear ()
int	size () const
int	number () const
bool	empty () const
void	realloc (int newSize)
void	check () const
Private Member Functions
int	leftSon (int i) const
int	rightSon (int i) const
int	father (int i) const
void	heapify (int i)
Private Attributes
ABA_GLOBAL *	glob_
ABA_ARRAY< Type >	heap_
ABA_ARRAY< Key >	keys_
int	n_
Friends
ostream &	operator<< (ostream &out, const ABA_BHEAP< Type, Key > &rhs)
	The output operator writes the elements of the heap together with their keys on an output stream.

---

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.

---

Constructor & Destructor Documentation

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.

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 for 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.

---

Member Function Documentation

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.

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].

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].

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.

template<class Type, class Key>

void ABA_BHEAP< Type, Key >::clear

(

)

Empties the heap.

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.

template<class Type, class Key>

int ABA_BHEAP< Type, Key >::number

(

)

const

Returns:

The number of elements in the heap.

template<class Type, class Key>

bool ABA_BHEAP< Type, Key >::empty

(

)

const

Returns:

true If there are no elements in the heap,

false otherwise.

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.

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.

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.

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.

template<class Type, class Key>

int ABA_BHEAP< Type, Key >::father

(

int

i

)

const [private]

Returns the index of the father of element i.

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.

---

Friends And Related Function Documentation

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.

---

Member Data Documentation

template<class Type, class Key>

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

Definition at line 216 of file bheap.h.

template<class Type, class Key>

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

Definition at line 217 of file bheap.h.

template<class Type, class Key>

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

Definition at line 218 of file bheap.h.

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:

• Include/abacus/bheap.h

---