BinaryHeap Class Reference

Binary heap implementation. More...

Detailed Description

Binary heap implementation.

Binary heaps are really fast for ordering nodes in a way that makes it possible to get the node with the lowest F score. Also known as a priority queue.

This has actually been rewritten as a 4-ary heap for performance, but it's the same principle.

See also

http://en.wikipedia.org/wiki/Binary_heap

https://en.wikipedia.org/wiki/D-ary_heap

Classes
struct	Tuple
	Item in the heap. More...

Public Member Functions
	BinaryHeap (int capacity)
	Create a new heap with the specified initial capacity. More...
void	Add (PathNode node)
	Adds a node to the heap. More...
void	Clear ()
	Removes all elements from the heap. More...
void	Rebuild ()
	Rebuilds the heap by trickeling down all items. More...
PathNode	Remove ()
	Returns the node with the lowest F score from the heap. More...

Public Attributes
float	growthFactor = 2
	The tree will grow by at least this factor every time it is expanded. More...
const ushort	NotInHeap = 0xFFFF
int	numberOfItems
	Number of items in the tree. More...

Package Functions
PathNode	GetNode (int i)
void	SetF (int i, uint f)

Properties
bool	isEmpty [get]
	True if the heap does not contain any elements. More...

Private Member Functions
void	DecreaseKey (Tuple node, ushort index)
void	Expand ()
	Expands to a larger backing array when the current one is too small. More...
void	Validate ()

Static Private Member Functions
static int	RoundUpToNextMultipleMod1 (int v)
	Rounds up v so that it has remainder 1 when divided by D. More...

Private Attributes
const int	D = 4
	Number of children of each node in the tree. More...
Tuple []	heap
	Internal backing array for the heap. More...
const bool	SortGScores = true
	Sort nodes by G score if there is a tie when comparing the F score. More...

Constructor & Destructor Documentation

BinaryHeap()

BinaryHeap

(

int

capacity

)

Create a new heap with the specified initial capacity.

Member Function Documentation

Add()

void Add

(

PathNode

node

)

Adds a node to the heap.

Clear()

void Clear

(

)

Removes all elements from the heap.

DecreaseKey()

void DecreaseKey ( Tuple  node, ushort  index  )

private

Expand()

void Expand ( )

private

Expands to a larger backing array when the current one is too small.

GetNode()

PathNode GetNode ( int  i )

package

Rebuild()

void Rebuild

(

)

Rebuilds the heap by trickeling down all items.

Usually called after the hTarget on a path has been changed

Remove()

PathNode Remove

(

)

Returns the node with the lowest F score from the heap.

RoundUpToNextMultipleMod1()

static int RoundUpToNextMultipleMod1 ( int  v )

staticprivate

Rounds up v so that it has remainder 1 when divided by D.

I.e it is of the form n*D + 1 where n is any non-negative integer.

SetF()

void SetF ( int  i, uint  f  )

package

Validate()

void Validate ( )

private

Member Data Documentation

D

const int D = 4

private

Number of children of each node in the tree.

Different values have been tested and 4 has been empirically found to perform the best.

See also

https://en.wikipedia.org/wiki/D-ary_heap

growthFactor

float growthFactor = 2

The tree will grow by at least this factor every time it is expanded.

heap

Tuple [] heap

private

Internal backing array for the heap.

NotInHeap

const ushort NotInHeap = 0xFFFF

numberOfItems

int numberOfItems

Number of items in the tree.

SortGScores

const bool SortGScores = true

private

Sort nodes by G score if there is a tie when comparing the F score.

Disabling this will improve pathfinding performance with around 2.5% but may break ties between paths that have the same length in a less desirable manner (only relevant for grid graphs).

Property Documentation

isEmpty

bool isEmpty

get

True if the heap does not contain any elements.

---

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

• /Users/arong/Unity/a-pathfinding-project/Assets/AstarPathfindingProject/Core/Misc/BinaryHeap.cs