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:

mapping[i][0] stores the index of the node currently stored in the i-th position of the tree.
mapping[i][1] stores the current position in the tree of the i-th node

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

Template parameter T1 is used for labelling tree nodes, and can be any copy-constructible type.

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_label	flag for using node labelling (true) or not (false).
[in]	map_	(default = NULL) pointer to map between the original->current element positions

Definition at line 885 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]	maxstack	size of memory reserve.
[in]	flag_label	flag for using node labelling (true) or not (false).
[in]	map_	(default = NULL) pointer to map between the original->current element positions

Definition at line 935 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 981 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 1219 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 1039 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] out output stream

Definition at line 1619 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] root value of element at tree root.

Definition at line 1330 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]	root	value of element at tree root.
[in,out]	root_label	label associated to root element (available only if flag_label is set to 'true' at heap construction)

Definition at line 1270 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_new value of the new element.

Definition at line 1435 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_new	value of the new element.
[in]	label_new	label associated to the new element (available only if flag_label is set to 'true' at heap construction)

Definition at line 1386 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]	i	index of element in the tree.
[in]	key_new	new value of the element.

Definition at line 1557 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]	i	index of element in the tree.
[in]	key_new	new value of the element.
[in]	label_new	new label to assign to the element (available only if flag_label is set to 'true' at heap construction)

Definition at line 1481 of file PQueue.tpp.