BinaryHeapM 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 d-ary heap (by default 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

Public Member Functions
	BinaryHeapM (int numberOfElements)
void	Add (PathNode node)
	Adds a node to the heap.
void	Clear ()
void	Rebuild ()
	Rebuilds the heap by trickeling down all items.
PathNode	Remove ()
	Returns the node with the lowest F score from the heap.

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

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

Private Member Functions
void	Validate ()

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

Constructor & Destructor Documentation

BinaryHeapM

(

int

numberOfElements

)

Member Function Documentation

void Add

(

PathNode

node

)

Adds a node to the heap.

void Clear

(

)

PathNode GetNode ( int  i )

package

void Rebuild

(

)

Rebuilds the heap by trickeling down all items.

Usually called after the hTarget on a path has been changed

PathNode Remove

(

)

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

void SetF ( int  i, uint  f  )

package

void Validate ( )

private

Member Data Documentation

Tuple [] binaryHeap

private

Internal backing array for the tree.

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

float growthFactor = 2

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

int numberOfItems

Number of items in the tree.

const bool SortGScores = true

private

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

---

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

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