All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Public Member Functions | Protected Member Functions | List of all members
Aux::PrioQueue< Key, Value > Class Template Reference

Priority queue with extract-min and decrease-key. More...

#include <PrioQueue.h>

Public Member Functions

 PrioQueue (const std::vector< Key > &keys)
 Builds priority queue from the vector keys, values are indices of keys. More...
 
 PrioQueue (uint64_t capacity)
 Builds priority queue of the specified capacity capacity. More...
 
virtual ~PrioQueue ()=default
 Default destructor. More...
 
virtual void insert (Key key, Value value)
 Inserts key-value pair stored in elem. More...
 
virtual ElemType extractMin ()
 Removes the element with minimum key and returns it. More...
 
virtual void changeKey (Key newKey, Value value)
 Modifies entry with value value. More...
 
virtual void decreaseKey (Key newKey, Value value)
 
virtual uint64_t size () const
 
virtual void remove (const Value &val)
 Removes key-value pair given by value val. More...
 
virtual void print ()
 DEBUGGING. More...
 

Protected Member Functions

 PrioQueue ()=default
 Default constructor without functionality. More...
 
virtual void remove (const ElemType &elem)
 Removes key-value pair given by elem. More...
 
virtual std::set< std::pair
< Key, Value > > 
content () const
 

Detailed Description

template<class Key, class Value>
class Aux::PrioQueue< Key, Value >

Priority queue with extract-min and decrease-key.

The type Val takes on integer values between 0 and n-1. O(n log n) for construction, O(log n) for typical operations.

Constructor & Destructor Documentation

template<class Key, class Value>
Aux::PrioQueue< Key, Value >::PrioQueue ( )
protecteddefault

Default constructor without functionality.

Only here for derived classes!

template<class Key, class Value >
Aux::PrioQueue< Key, Value >::PrioQueue ( const std::vector< Key > &  keys)

Builds priority queue from the vector keys, values are indices of keys.

template<class Key, class Value >
Aux::PrioQueue< Key, Value >::PrioQueue ( uint64_t  capacity)

Builds priority queue of the specified capacity capacity.

template<class Key, class Value>
virtual Aux::PrioQueue< Key, Value >::~PrioQueue ( )
virtualdefault

Default destructor.

Member Function Documentation

template<class Key, class Value>
void Aux::PrioQueue< Key, Value >::changeKey ( Key  newKey,
Value  value 
)
inlinevirtual

Modifies entry with value value.

The entry is then set to newKey with the same value. If the corresponding key is not present, the element will be inserted.

Reimplemented in Aux::BucketPQ.

template<class Key , class Value >
std::set< std::pair< Key, Value > > Aux::PrioQueue< Key, Value >::content ( ) const
inlineprotectedvirtual
Returns
current content of queue
template<class Key, class Value>
virtual void Aux::PrioQueue< Key, Value >::decreaseKey ( Key  newKey,
Value  value 
)
inlinevirtual
template<class Key , class Value >
std::pair< Key, Value > Aux::PrioQueue< Key, Value >::extractMin ( )
virtual

Removes the element with minimum key and returns it.

Reimplemented in Aux::BucketPQ.

template<class Key, class Value>
void Aux::PrioQueue< Key, Value >::insert ( Key  key,
Value  value 
)
inlinevirtual

Inserts key-value pair stored in elem.

Reimplemented in Aux::BucketPQ.

template<class Key, class Value>
virtual void Aux::PrioQueue< Key, Value >::print ( )
inlinevirtual

DEBUGGING.

template<class Key , class Value >
void Aux::PrioQueue< Key, Value >::remove ( const ElemType &  elem)
inlineprotectedvirtual

Removes key-value pair given by elem.

template<class Key , class Value>
void Aux::PrioQueue< Key, Value >::remove ( const Value &  val)
inlinevirtual

Removes key-value pair given by value val.

Reimplemented in Aux::BucketPQ.

template<class Key , class Value >
uint64_t Aux::PrioQueue< Key, Value >::size ( ) const
inlinevirtual
Returns
Number of elements in PQ.

Reimplemented in Aux::BucketPQ.


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