PriorityQueueBinaryHeap< T, Key, GetKey, CompareKeys, Sequence > Class Template Reference

A priority queue implemented with a binary heap. More...

#include <PriorityQueueBinaryHeap.h>

Inheritance diagram for PriorityQueueBinaryHeap< T, Key, GetKey, CompareKeys, Sequence >:
PriorityQueue< T, Key, GetKey, CompareKeys, Sequence >

List of all members.

Public Types

typedef base_type::element_type element_type
 The element type.
typedef base_type::const_reference const_reference
 A const reference to the element type.
typedef base_type::key_type key_type
 The key type.
typedef base_type::size_type size_type
 The size type.
typedef base_type::value_type value_type
 The type stored in the binary heap.

Public Member Functions

 PriorityQueueBinaryHeap (const sequence_type &container=sequence_type())
 Make from a container of values.
 PriorityQueueBinaryHeap (size_type n)
 Construct and reserve memory for n elements.
template<class InputIterator >
 PriorityQueueBinaryHeap (InputIterator first, InputIterator last, const sequence_type &container=sequence_type())
 Add the values in the range to the container and then make the heap.
virtual ~PriorityQueueBinaryHeap ()
 Destructor.
size_type size () const
 Return the number of elements in the priority queue.
bool empty () const
 Return true if the priority queue is empty.
const_reference top () const
 Return the element at the top of the priority queue.
void push (element_type x)
 Add an element to the priority queue.
void pop ()
 Remove the element at the top of the priority queue.

Protected Attributes

compare_values_functor _compare
 The value type comparison functor.
sequence_type _container
 The container for storing the values.

Detailed Description

template<typename T, typename Key = typename std::iterator_traits<T>::value_type, class GetKey = Dereference<T>, class CompareKeys = std::greater<Key>, class Sequence = std::vector<T>>
class PriorityQueueBinaryHeap< T, Key, GetKey, CompareKeys, Sequence >

A priority queue implemented with a binary heap.

This priority queue provides the same functionality as the STL class std::priority_queue, however the template parameters are a little different. The element type is the only required parameter. The remaining parameters have default values. By default, it is assumed that the element type is a handle and that the key is obtained by dereferencing this handle.

The implementation uses the following STL heap functions.

This priority queue does not support dynamic keys. The key values are not allowed to change while an element is in the queue.

Parameters:
T is the element type.
Key is the key type. By default, it is assumed that the element type is handle and the key type is the value type of the handle.
GetKey is the functor that gets the key from the element. Note that the binary heap does not store the keys. Thus it relies on the GetKey functor for heap operations.
CompareKeys is a functor that takes two keys as arguments and returns a boolean. It is used to order the objects in the priority queue. For greater than comparisons, the top of the priority queue holds the element with minimum key. This is the default behavior.
Sequence is the container for the binary heap. It is std::vector<T> by default.

Constructor & Destructor Documentation

template<typename T , typename Key = typename std::iterator_traits<T>::value_type, class GetKey = Dereference<T>, class CompareKeys = std::greater<Key>, class Sequence = std::vector<T>>
PriorityQueueBinaryHeap< T, Key, GetKey, CompareKeys, Sequence >::PriorityQueueBinaryHeap ( const sequence_type &  container = sequence_type()  )  [inline, explicit]

Make from a container of values.

The default constructor makes an empty queue.


The documentation for this class was generated from the following file:
Generated on Thu Jun 30 02:14:52 2016 for Algorithms and Data Structures Package by  doxygen 1.6.3