class for min priority queue. More...

Public Member Functions
	MinPQueue (bool a=false, std::vector< std::array< int, 2 > > *b=NULL)

	MinPQueue (int, bool a=false, std::vector< std::array< int, 2 > > *b=NULL)

	~MinPQueue (void)

void	buildHeap (void)

void	clear (void)

void	display (std::ostream &)

void	extract (T &)

void	extract (T &, T1 &)

void	insert (T &)

void	insert (T &, T1 &)

void	modify (int, T &)

void	modify (int, T &, T1 &)

Public Attributes
int	heap_size

std::vector< T >	keys

std::vector< T1 >	labels

std::vector< std::array< int, 2 > > *	map

int	MAXSTK

Detailed Description

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

class for min priority queue.

Class for priority element insertion and extraction. Elements inserted in a min. 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 smallest 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 163 of file SortAlgorithms.hpp.

Constructor & Destructor Documentation

◆ MinPQueue() [1/2]

template<class T , class T1 >

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

Default constructor for class MinPQueue. 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 85 of file PQueue.tpp.

◆ MinPQueue() [2/2]

template<class T , class T1 >

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

Constructor #1 for class MinPQueue. 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 135 of file PQueue.tpp.

◆ ~MinPQueue()

template<class T , class T1 >

bitpit::MinPQueue< T, T1 >::~MinPQueue ( void )

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

Definition at line 181 of file PQueue.tpp.

Member Function Documentation

◆ buildHeap()

template<class T , class T1 >

void bitpit::MinPQueue< T, T1 >::buildHeap ( void )

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

Definition at line 387 of file PQueue.tpp.

◆ clear()

template<class T , class T1 >

void bitpit::MinPQueue< T, T1 >::clear ( void )

Clear current content without freeing memory.

Definition at line 223 of file PQueue.tpp.

◆ display()

template<class T , class T1 >

void bitpit::MinPQueue< 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 787 of file PQueue.tpp.

◆ extract() [1/2]

template<class T , class T1 >

void bitpit::MinPQueue< 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 482 of file PQueue.tpp.

◆ extract() [2/2]

template<class T , class T1 >

void bitpit::MinPQueue< 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 422 of file PQueue.tpp.

◆ insert() [1/2]

template<class T , class T1 >

void bitpit::MinPQueue< 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 587 of file PQueue.tpp.

◆ insert() [2/2]

template<class T , class T1 >

void bitpit::MinPQueue< 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 538 of file PQueue.tpp.

◆ modify() [1/2]

template<class T , class T1 >

void bitpit::MinPQueue< 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 725 of file PQueue.tpp.

◆ modify() [2/2]

template<class T , class T1 >

void bitpit::MinPQueue< 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 649 of file PQueue.tpp.