bin_heap< T, Pred > Class Template Reference

Binary heap. More...

#include <JETSCAPE/blob/main/external_packages/gtl/include/GTL/bin_heap.h>

Collaboration diagram for bin_heap< T, Pred >:

Public Member Functions
	bin_heap (const Pred &prd)
	Creates empty binary heap.
	bin_heap (const Pred &prd, const int est_size)
	Creates empty binary heap.
	bin_heap (const bin_heap< T, Pred > &bh)
	Copy constructor.
bin_heap< T, Pred > &	operator= (const bin_heap< T, Pred > &bh)
	Assigns bh to this binary heap.
	~bin_heap ()
	Destructor.
void	push (const T &ins)
	Inserts ins in heap.
void	pop ()
	Removes the element on top of the heap.
const T &	top () const
	Returns a reference to the element at the top of the heap.
void	changeKey (const T &cha)
	Reconstructs heap condition after changing key value of cha externally.
bool	is_empty () const
	Checks if heap is empty.
void	clear ()

Private Member Functions
void	bubble_up (heap_node< T > *const n)
void	bubble_down (heap_node< T > *const n)

Private Attributes
const Pred &	prd
int	size
int	capacity
vector< heap_node< T > * >	container
map< T, heap_node< T > * >	heap_node_map

Detailed Description

template<class T, class Pred>
class bin_heap< T, Pred >

Binary heap.

Author

Christian Bachmaier chris.nosp@m.@inf.nosp@m.osun..nosp@m.fmi..nosp@m.uni-p.nosp@m.assa.nosp@m.u.de

Definition at line 63 of file bin_heap.h.

View newest version in sPHENIX GitHub at line 63 of file bin_heap.h

Constructor & Destructor Documentation

template<class T , class Pred >

bin_heap< T, Pred >::bin_heap

(

const Pred &

prd

)

Creates empty binary heap.

Parameters

prd	binary predicate to compare two Ts

Definition at line 206 of file bin_heap.h.

View newest version in sPHENIX GitHub at line 206 of file bin_heap.h

References bin_heap< T, Pred >::capacity, and bin_heap< T, Pred >::container.

template<class T , class Pred >

bin_heap< T, Pred >::bin_heap	(	const Pred &	prd,
		const int	est_size
	)

Creates empty binary heap.

Parameters

prd	binary predicate to compare two Ts
est_size	estimated maximal size of heap

Definition at line 214 of file bin_heap.h.

View newest version in sPHENIX GitHub at line 214 of file bin_heap.h

References bin_heap< T, Pred >::capacity, and bin_heap< T, Pred >::container.

template<class T , class Pred >

bin_heap< T, Pred >::bin_heap

(

const bin_heap< T, Pred > &

bh

)

Copy constructor.

Parameters

bh	binary heap to copy

Definition at line 226 of file bin_heap.h.

View newest version in sPHENIX GitHub at line 226 of file bin_heap.h

References bin_heap< T, Pred >::capacity, bin_heap< T, Pred >::container, i, and bin_heap< T, Pred >::size.

template<class T , class Pred >

bin_heap< T, Pred >::~bin_heap

(

)

Destructor.

Definition at line 257 of file bin_heap.h.

View newest version in sPHENIX GitHub at line 257 of file bin_heap.h

Member Function Documentation

template<class T , class Pred >

void bin_heap< T, Pred >::bubble_down ( heap_node< T > *const  n )

private

Definition at line 369 of file bin_heap.h.

View newest version in sPHENIX GitHub at line 369 of file bin_heap.h

References container, configureMap::data, heap_node< T >::data, j, n, heap_node< T >::pos, Acts::Test::pos, and size.

template<class T , class Pred >

void bin_heap< T, Pred >::bubble_up ( heap_node< T > *const  n )

private

Definition at line 349 of file bin_heap.h.

View newest version in sPHENIX GitHub at line 349 of file bin_heap.h

References container, heap_node< T >::data, n, heap_node< T >::pos, and Acts::Test::pos.

template<class T , class Pred >

void bin_heap< T, Pred >::changeKey

(

const T &

cha

)

Reconstructs heap condition after changing key value of cha externally.

Parameters

cha	element with changed key value

Note

changeKey doesn't operate if cha is a primitive data structure, because it represents its key value itself, or if one object is stored more than once in the data structure.

See Also

dijkstra

Definition at line 311 of file bin_heap.h.

View newest version in sPHENIX GitHub at line 311 of file bin_heap.h

References container, heap_node< T >::data, n, and Acts::Test::pos.

template<class T , class Pred >

void bin_heap< T, Pred >::clear

(

)

Definition at line 337 of file bin_heap.h.

View newest version in sPHENIX GitHub at line 337 of file bin_heap.h

References container, i, and size.

template<class T , class Pred >

bool bin_heap< T, Pred >::is_empty

(

)

const

Checks if heap is empty.

Returns

true iff empty

Definition at line 329 of file bin_heap.h.

View newest version in sPHENIX GitHub at line 329 of file bin_heap.h

References size.

template<class T , class Pred >

bin_heap< T, Pred > & bin_heap< T, Pred >::operator=

(

const bin_heap< T, Pred > &

bh

)

Assigns bh to this binary heap.

All elements in this heap will be deleted. The predicate of this heap must be physically the same as the one of bh.

Parameters

bh	binary heap

Returns

this heap

Definition at line 238 of file bin_heap.h.

View newest version in sPHENIX GitHub at line 238 of file bin_heap.h

References assert, bin_heap< T, Pred >::capacity, container, bin_heap< T, Pred >::container, i, bin_heap< T, Pred >::prd, bin_heap< T, Pred >::size, and size.

template<class T , class Pred >

void bin_heap< T, Pred >::pop

(

)

Removes the element on top of the heap.

Definition at line 282 of file bin_heap.h.

View newest version in sPHENIX GitHub at line 282 of file bin_heap.h

References assert, container, configureMap::data, and size.

template<class T , class Pred >

void bin_heap< T, Pred >::push

(

const T &

ins

)

Inserts ins in heap.

Parameters

ins	data element to be inserted

Definition at line 264 of file bin_heap.h.

View newest version in sPHENIX GitHub at line 264 of file bin_heap.h

References container, n, heap_node< T >::pos, and size.

template<class T , class Pred >

const T & bin_heap< T, Pred >::top

(

)

const

Returns a reference to the element at the top of the heap.

Returns

top element of the heap

Definition at line 304 of file bin_heap.h.

View newest version in sPHENIX GitHub at line 304 of file bin_heap.h

References container.

Referenced by pypdel(), pypdfu(), structm(), structmold(), structp(), and structpold().

Here is the caller graph for this function:

Member Data Documentation

template<class T, class Pred>

int bin_heap< T, Pred >::capacity

private

Definition at line 168 of file bin_heap.h.

View newest version in sPHENIX GitHub at line 168 of file bin_heap.h

Referenced by bin_heap< T, Pred >::bin_heap(), and bin_heap< T, Pred >::operator=().

template<class T, class Pred>

vector<heap_node<T>* > bin_heap< T, Pred >::container

private

Definition at line 174 of file bin_heap.h.

View newest version in sPHENIX GitHub at line 174 of file bin_heap.h

Referenced by bin_heap< T, Pred >::bin_heap(), and bin_heap< T, Pred >::operator=().

template<class T, class Pred>

map<T, heap_node<T>* > bin_heap< T, Pred >::heap_node_map

private

Definition at line 180 of file bin_heap.h.

View newest version in sPHENIX GitHub at line 180 of file bin_heap.h

template<class T, class Pred>

const Pred& bin_heap< T, Pred >::prd

private

Definition at line 155 of file bin_heap.h.

View newest version in sPHENIX GitHub at line 155 of file bin_heap.h

Referenced by bin_heap< T, Pred >::operator=().

template<class T, class Pred>

int bin_heap< T, Pred >::size

private

Definition at line 161 of file bin_heap.h.

View newest version in sPHENIX GitHub at line 161 of file bin_heap.h

Referenced by bin_heap< T, Pred >::bin_heap(), and bin_heap< T, Pred >::operator=().

---

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

• JETSCAPE/blob/main/external_packages/gtl/include/GTL/bin_heap.h