tdc::ArrayMaxHeap< array_t > Class Template Reference

Represents a binary max heap backed by an external array of keys. More...

#include <ArrayMaxHeap.hpp>

Public Member Functions
	ArrayMaxHeap (array_t &array, const size_t array_size, const size_t heap_size)
	Default constructor. More...
void	insert (len_t i)
	Inserts an item into the heap. More...
void	remove (len_t i)
	Removes an item from the heap. More...
template<typename key_t >
void	decrease_key (len_t i, key_t value)
	Decreases the key of item in the heap. More...
bool	contains (len_t i) const
	Checks whether or not an item is contained in this heap. More...
size_t	size () const
	Yields the number of items currently stored in the heap. More...
size_t	get_max () const
	Gets the first (maximum) item from the heap. More...
size_t	top () const
	Gets the top (first, maximum) item from the heap. More...
len_t	key (len_t i) const
	Gets an item's key. More...

Detailed Description

template<typename array_t>
class tdc::ArrayMaxHeap< array_t >

Represents a binary max heap backed by an external array of keys.

The max heap induces an order on the indices of the key array it is backed by. The first element of the heap is the index of the largest item in the key array.

Template Parameters

array_t

The key array type. Must support the [] operator.

Definition at line 17 of file ArrayMaxHeap.hpp.

Constructor & Destructor Documentation

ArrayMaxHeap()

template<typename array_t >

tdc::ArrayMaxHeap< array_t >::ArrayMaxHeap ( array_t &  array, const size_t  array_size, const size_t  heap_size  )

inline

Default constructor.

Note that the constructor will not insert any items into the heap and serves merely for initialization.

Parameters

array	The array of keys sorted by this heap.
array_size	The size of the key array.
heap_size	The maximum amount of items stored in the heap.

Definition at line 65 of file ArrayMaxHeap.hpp.

Member Function Documentation

contains()

template<typename array_t >

bool tdc::ArrayMaxHeap< array_t >::contains ( len_t  i ) const

inline

Checks whether or not an item is contained in this heap.

Parameters

i	The index of the item in the key array.

Returns

true if the item is contained in the heap, false otherwise.

Definition at line 198 of file ArrayMaxHeap.hpp.

decrease_key()

template<typename array_t >

template<typename key_t >

void tdc::ArrayMaxHeap< array_t >::decrease_key ( len_t  i, key_t  value  )

inline

Decreases the key of item in the heap.

Template Parameters

key_t

the key type.

Parameters

i	The index of the item in the key array. The key is retrieved from there.
value	The new key value.

Definition at line 177 of file ArrayMaxHeap.hpp.

get_max()

template<typename array_t >

size_t tdc::ArrayMaxHeap< array_t >::get_max ( ) const

inline

Gets the first (maximum) item from the heap.

Returns

The index in the key array that points to the largest key.

Definition at line 210 of file ArrayMaxHeap.hpp.

insert()

template<typename array_t >

void tdc::ArrayMaxHeap< array_t >::insert ( len_t  i )

inline

Inserts an item into the heap.

Parameters

i	The index of the item in the key array. The key is retrieved from there.

Definition at line 77 of file ArrayMaxHeap.hpp.

key()

template<typename array_t >

len_t tdc::ArrayMaxHeap< array_t >::key ( len_t  i ) const

inline

Gets an item's key.

Parameters

i	The index of the item in the key array.

Returns

The item's key, retrieved from the key array.

Definition at line 224 of file ArrayMaxHeap.hpp.

remove()

template<typename array_t >

void tdc::ArrayMaxHeap< array_t >::remove ( len_t  i )

inline

Removes an item from the heap.

Parameters

i	The index of the item in the key array. The key is retrieved from there.

Definition at line 152 of file ArrayMaxHeap.hpp.

size()

template<typename array_t >

size_t tdc::ArrayMaxHeap< array_t >::size ( ) const

inline

Yields the number of items currently stored in the heap.

Returns

The number of items currently stored in the heap.

Definition at line 204 of file ArrayMaxHeap.hpp.

top()

template<typename array_t >

size_t tdc::ArrayMaxHeap< array_t >::top ( ) const

inline

Gets the top (first, maximum) item from the heap.

Returns

The index in the key array that points to the largest key.

Definition at line 216 of file ArrayMaxHeap.hpp.

---

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

• ArrayMaxHeap.hpp