tudocomp
– The TU Dortmund Compression Framework
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_tThe key array type. Must support the [] operator.

Definition at line 17 of file ArrayMaxHeap.hpp.

Constructor & Destructor Documentation

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
arrayThe array of keys sorted by this heap.
array_sizeThe size of the key array.
heap_sizeThe maximum amount of items stored in the heap.

Definition at line 65 of file ArrayMaxHeap.hpp.

Member Function Documentation

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

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_tthe key type.
Parameters
iThe index of the item in the key array. The key is retrieved from there.
valueThe new key value.

Definition at line 177 of file ArrayMaxHeap.hpp.

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.

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

Inserts an item into the heap.

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

Definition at line 77 of file ArrayMaxHeap.hpp.

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

Gets an item's key.

Parameters
iThe 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.

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

Removes an item from the heap.

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

Definition at line 152 of file ArrayMaxHeap.hpp.

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.

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: