Binary Heap as C++ template. More...

#include <binaryheap.hpp>

Public Member Functions
	CBinaryHeapT (size_t initial_capacity)
	Create a binary heap.

size_t	Length () const
	Get the number of items stored in the priority queue.

bool	IsEmpty () const
	Test if the priority queue is empty.

T *	Begin ()
	Get the smallest item in the binary tree.

T *	End ()
	Get the LAST item in the binary tree.

void	Include (T *new_item)
	Insert new item into the priority queue, maintaining heap order.

T *	Shift ()
	Remove and return the smallest (and also first) item from the priority queue.

void	Remove (size_t index)
	Remove item at given index from the priority queue.

size_t	FindIndex (const T &item) const
	Search for an item in the priority queue.

void	Clear ()
	Make the priority queue empty.

Protected Member Functions
size_t	HeapifyDown (size_t gap, T *item)
	Get position for fixing a gap (downwards).

size_t	HeapifyUp (size_t gap, T *item)
	Get position for fixing a gap (upwards).

Private Attributes
size_t	items = 0
	Number of valid items in the heap.

std::vector< T * >	data
	The pointer to the heap item pointers.

Detailed Description

template<class T>
class CBinaryHeapT< T >

Binary Heap as C++ template.

A carrier which keeps its items automatically holds the smallest item at the first position. The order of items is maintained by using a binary tree. The implementation is used for priority queues.

There are two major differences compared to std::priority_queue. First the std::priority_queue does not support indexing/removing elements in the middle of the heap/queue and second it has the biggest item first.

Usage information:: Item of the binary heap should support the 'lower-than' operator '<'. It is used for comparing items before moving them to their position.

: This binary heap allocates just the space for item pointers. The items are allocated elsewhere.

Implementation notes:: Internally the first item is never used, because that simplifies the implementation.

: For further information about the Binary Heap algorithm, see http://www.policyalmanac.org/games/binaryHeaps.htm

Template Parameters

T	Type of the items stored in the binary heap

Definition at line 53 of file binaryheap.hpp.

Constructor & Destructor Documentation

◆ CBinaryHeapT()

template<class T >

CBinaryHeapT< T >::CBinaryHeapT ( size_t initial_capacity )

inlineexplicit

Create a binary heap.

Parameters

initial_capacity The initial reserved capacity for the heap.

Definition at line 63 of file binaryheap.hpp.

References CBinaryHeapT< T >::Clear().

Member Function Documentation

◆ Begin()

template<class T >

T * CBinaryHeapT< T >::Begin ( )

inline

Get the smallest item in the binary tree.

Returns: The smallest item, or throw assert if empty.

Definition at line 172 of file binaryheap.hpp.

References CBinaryHeapT< T >::IsEmpty().

Referenced by NodeList< Titem, Thash_bits_open, Thash_bits_closed >::GetBestOpenNode(), and CBinaryHeapT< T >::Shift().

◆ Clear()

template<class T >

void CBinaryHeapT< T >::Clear ( )

inline

Make the priority queue empty.

All remaining items will remain untouched.

Definition at line 273 of file binaryheap.hpp.

References CHECK_CONSISTY.

Referenced by CBinaryHeapT< T >::CBinaryHeapT().

◆ End()

template<class T >

T * CBinaryHeapT< T >::End ( )

inline

Get the LAST item in the binary tree.

Note: The last item is not necessary the biggest!

Returns: The last item

Definition at line 185 of file binaryheap.hpp.

References CBinaryHeapT< T >::items.

Referenced by CBinaryHeapT< T >::Remove(), and CBinaryHeapT< T >::Shift().

◆ FindIndex()

template<class T >

size_t CBinaryHeapT< T >::FindIndex ( const T & item ) const

inline

Search for an item in the priority queue.

Matching is done by comparing address of the item.

Parameters

item	The reference to the item

Returns: The index of the item or zero if not found

Definition at line 263 of file binaryheap.hpp.

Referenced by NodeList< Titem, Thash_bits_open, Thash_bits_closed >::PopOpenNode().

◆ HeapifyDown()

template<class T >

size_t CBinaryHeapT< T >::HeapifyDown	(	size_t	gap,
		T *	item
	)

inlineprotected

Get position for fixing a gap (downwards).

The gap is moved downwards in the binary tree until it is in order again.

Parameters

gap	The position of the gap
item	The proposed item for filling the gap

Returns: The (gap)position where the item fits

Definition at line 79 of file binaryheap.hpp.

References CBinaryHeapT< T >::items.

Referenced by CBinaryHeapT< T >::Remove(), and CBinaryHeapT< T >::Shift().

◆ HeapifyUp()

template<class T >

size_t CBinaryHeapT< T >::HeapifyUp	(	size_t	gap,
		T *	item
	)

inlineprotected

Get position for fixing a gap (upwards).

The gap is moved upwards in the binary tree until the is in order again.

Parameters

gap	The position of the gap
item	The proposed item for filling the gap

Returns: The (gap)position where the item fits

Definition at line 115 of file binaryheap.hpp.

References CBinaryHeapT< T >::data.

Referenced by CBinaryHeapT< T >::Include(), and CBinaryHeapT< T >::Remove().

◆ Include()

template<class T >

void CBinaryHeapT< T >::Include ( T * new_item )

inline

Insert new item into the priority queue, maintaining heap order.

Parameters

new_item The pointer to the new item

Definition at line 195 of file binaryheap.hpp.

References CHECK_CONSISTY, and CBinaryHeapT< T >::HeapifyUp().

Referenced by NodeList< Titem, Thash_bits_open, Thash_bits_closed >::InsertOpenNode().

◆ IsEmpty()

template<class T >

bool CBinaryHeapT< T >::IsEmpty ( ) const

inline

Test if the priority queue is empty.

Returns: True if empty

Definition at line 162 of file binaryheap.hpp.

Referenced by CBinaryHeapT< T >::Begin(), NodeList< Titem, Thash_bits_open, Thash_bits_closed >::GetBestOpenNode(), NodeList< Titem, Thash_bits_open, Thash_bits_closed >::PopBestOpenNode(), CBinaryHeapT< T >::Remove(), and CBinaryHeapT< T >::Shift().

◆ Length()

template<class T >

size_t CBinaryHeapT< T >::Length ( ) const

inline

Get the number of items stored in the priority queue.

Returns: The number of items in the queue

Definition at line 152 of file binaryheap.hpp.

References CBinaryHeapT< T >::items.

◆ Remove()

template<class T >

void CBinaryHeapT< T >::Remove ( size_t index )

inline

Remove item at given index from the priority queue.

Parameters

index The position of the item in the heap

Definition at line 233 of file binaryheap.hpp.

References CHECK_CONSISTY, CBinaryHeapT< T >::End(), CBinaryHeapT< T >::HeapifyDown(), CBinaryHeapT< T >::HeapifyUp(), CBinaryHeapT< T >::IsEmpty(), and CBinaryHeapT< T >::items.

Referenced by NodeList< Titem, Thash_bits_open, Thash_bits_closed >::PopOpenNode().

◆ Shift()

template<class T >

T * CBinaryHeapT< T >::Shift ( )

inline

Remove and return the smallest (and also first) item from the priority queue.

Returns: The pointer to the removed item

Definition at line 210 of file binaryheap.hpp.

References CBinaryHeapT< T >::Begin(), CHECK_CONSISTY, CBinaryHeapT< T >::End(), CBinaryHeapT< T >::HeapifyDown(), and CBinaryHeapT< T >::IsEmpty().

Referenced by NodeList< Titem, Thash_bits_open, Thash_bits_closed >::PopBestOpenNode().

Field Documentation

◆ data

template<class T >

std::vector<T *> CBinaryHeapT< T >::data

private

The pointer to the heap item pointers.

Definition at line 56 of file binaryheap.hpp.

Referenced by CBinaryHeapT< T >::HeapifyUp().

◆ items

template<class T >

size_t CBinaryHeapT< T >::items = 0

private

Number of valid items in the heap.

Definition at line 55 of file binaryheap.hpp.

Referenced by CBinaryHeapT< T >::End(), CBinaryHeapT< T >::HeapifyDown(), CBinaryHeapT< T >::Length(), and CBinaryHeapT< T >::Remove().

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

src/misc/binaryheap.hpp

Public Member Functions

Protected Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ CBinaryHeapT()

Member Function Documentation

◆ Begin()

◆ Clear()

◆ End()

◆ FindIndex()

◆ HeapifyDown()

◆ HeapifyUp()

◆ Include()

◆ IsEmpty()

◆ Length()

◆ Remove()

◆ Shift()

Field Documentation

◆ data

◆ items