Loading...
Searching...
No Matches
Public Attributes | List of all members
bitpit::MaxPQueue< T, T1 > Class Template Reference

class for max priority queue. More...

Public Attributes

int heap_size
 
std::vector< T > keys
 
std::vector< T1 > labels
 
std::vector< std::array< int, 2 > > * map
 
int MAXSTK
 
 MaxPQueue (bool a=false, std::vector< std::array< int, 2 > > *b=NULL)
 
 MaxPQueue (int, bool a=false, std::vector< std::array< int, 2 > > *b=NULL)
 
 ~MaxPQueue (void)
 
void clear (void)
 
void extract (T &)
 
void extract (T &, T1 &)
 
void insert (T &)
 
void insert (T &, T1 &)
 
void modify (int, T &)
 
void modify (int, T &, T1 &)
 
void buildHeap (void)
 
void display (std::ostream &)
 

Detailed Description

template<class T, class T1 = T>
class bitpit::MaxPQueue< T, T1 >

class for max priority queue.

Class for priority element insertion and extraction. Elements inserted in a max. priority queue are internally sorted on a binary tree to ensure the following property (heap property): given a parent node in the tree (P), and given its children nodes (L and R), P > L and P > R. In this way, the root element is the one with the largest value in the tree.

Each time a new element is inserted or removed from the heap, the tree is updated by moving the elements upwards or downwards on each branch to maintain the heap property. The new position of elements in the tree can be tracked by passing a non-null pointer to a mapping (a vector< array<int, 2> >) to the heap constructor. At any time, the mapping will store the following information:

Template parameter T can be of any copy-constructible type for which operator< is defined

Definition at line 243 of file SortAlgorithms.hpp.

Constructor & Destructor Documentation

◆ MaxPQueue() [1/2]

template<class T , class T1 >
bitpit::MaxPQueue< T, T1 >::MaxPQueue ( bool flag_label = false,
std::vector< std::array< int, 2 > > * map_ = NULL )

Default constructor for class MaxPQueue. Initialize an empty priority queue. If a pointer to a vector<array<int, 2>> is provided, the mapping between the original and current element position in the tree is tracked.

Parameters
[in]flag_labelflag for using node labelling (true) or not (false).
[in]map_(default = NULL) pointer to map between the original->current element positions

Definition at line 887 of file PQueue.tpp.

◆ MaxPQueue() [2/2]

template<class T , class T1 >
bitpit::MaxPQueue< T, T1 >::MaxPQueue ( int maxstack,
bool flag_label = false,
std::vector< std::array< int, 2 > > * map_ = NULL )

Constructor #1 for class MaxPQueue. Initialize an empty priority queue. The size of memory reserve is specified by maxstack. If a pointer to a vector<array<int, 2>> is provided, the mapping between the original and current element position in the tree is tracked.

Parameters
[in]maxstacksize of memory reserve.
[in]flag_labelflag for using node labelling (true) or not (false).
[in]map_(default = NULL) pointer to map between the original->current element positions

Definition at line 937 of file PQueue.tpp.

◆ ~MaxPQueue()

template<class T , class T1 >
bitpit::MaxPQueue< T, T1 >::~MaxPQueue ( void )

Default destructor for class MaxPQueue. Clear queue content and free memory.

Definition at line 983 of file PQueue.tpp.

Member Function Documentation

◆ buildHeap()

template<class T , class T1 >
void bitpit::MaxPQueue< T, T1 >::buildHeap ( void )

Build a max heap, from data currently stored in the underlying container.

Definition at line 1221 of file PQueue.tpp.

◆ clear()

template<class T , class T1 >
void bitpit::MaxPQueue< T, T1 >::clear ( void )

Clear current content without freeing memory.

Definition at line 1041 of file PQueue.tpp.

◆ display()

template<class T , class T1 >
void bitpit::MaxPQueue< T, T1 >::display ( std::ostream & out)

Display info about the heap to output stream (e.g. current number of element stored in the tree, memory reserved, etc.)

Parameters
[in,out]outoutput stream

Definition at line 1621 of file PQueue.tpp.

◆ extract() [1/2]

template<class T , class T1 >
void bitpit::MaxPQueue< T, T1 >::extract ( T & root)

Extract the next element (i.e. the element on the root of the tree) from heap list and reduce heap size by one element. After extraction heap property is automatically restored by updating the tree.

Parameters
[in,out]rootvalue of element at tree root.

Definition at line 1332 of file PQueue.tpp.

◆ extract() [2/2]

template<class T , class T1 >
void bitpit::MaxPQueue< T, T1 >::extract ( T & root,
T1 & root_label )

Extract the next element (i.e. the element on the root of the tree) from heap list and reduce heap size by one element. After extraction heap property is automatically restored by updating the tree.

Parameters
[in,out]rootvalue of element at tree root.
[in,out]root_labellabel associated to root element (available only if flag_label is set to 'true' at heap construction)

Definition at line 1272 of file PQueue.tpp.

◆ insert() [1/2]

template<class T , class T1 >
void bitpit::MaxPQueue< T, T1 >::insert ( T & key_new)

Insert a new element in the heap. After insertion the heap property is automatically restored by updating the tree.

Parameters
[in]key_newvalue of the new element.

Definition at line 1437 of file PQueue.tpp.

◆ insert() [2/2]

template<class T , class T1 >
void bitpit::MaxPQueue< T, T1 >::insert ( T & key_new,
T1 & label_new )

Insert a new element in the heap. After insertion the heap property is automatically restored by updating the tree.

Parameters
[in]key_newvalue of the new element.
[in]label_newlabel associated to the new element (available only if flag_label is set to 'true' at heap construction)

Definition at line 1388 of file PQueue.tpp.

◆ modify() [1/2]

template<class T , class T1 >
void bitpit::MaxPQueue< T, T1 >::modify ( int i,
T & key_new )

Modify the value of an existing element in the heap. The heap property is automatically restored by moving down/upwards the element in the tree.

Parameters
[in]iindex of element in the tree.
[in]key_newnew value of the element.

Definition at line 1559 of file PQueue.tpp.

◆ modify() [2/2]

template<class T , class T1 >
void bitpit::MaxPQueue< T, T1 >::modify ( int i,
T & key_new,
T1 & label_new )

Modify the value of an existing element in the heap. The heap property is automatically restored by moving down/upwards the element in the tree.

Parameters
[in]iindex of element in the tree.
[in]key_newnew value of the element.
[in]label_newnew label to assign to the element (available only if flag_label is set to 'true' at heap construction)

Definition at line 1483 of file PQueue.tpp.

Member Data Documentation

◆ heap_size

template<class T , class T1 = T>
int bitpit::MaxPQueue< T, T1 >::heap_size

number of elements in stack

Definition at line 248 of file SortAlgorithms.hpp.

◆ keys

template<class T , class T1 = T>
std::vector< T > bitpit::MaxPQueue< T, T1 >::keys

stack

Definition at line 249 of file SortAlgorithms.hpp.

◆ labels

template<class T , class T1 = T>
std::vector< T1 > bitpit::MaxPQueue< T, T1 >::labels

labels associated to keys

Definition at line 250 of file SortAlgorithms.hpp.

◆ map

template<class T , class T1 = T>
std::vector< std::array<int,2> >* bitpit::MaxPQueue< T, T1 >::map

pointer to mapper

Definition at line 251 of file SortAlgorithms.hpp.

◆ MAXSTK

template<class T , class T1 = T>
int bitpit::MaxPQueue< T, T1 >::MAXSTK

Maximal stack size between resize

Definition at line 247 of file SortAlgorithms.hpp.


The documentation for this class was generated from the following files:
--- layout: doxygen_footer ---