Struct BinaryHeap

Public

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.

Inner Types

Item in the heap.

Public Methods

Add (nodes, pathNodeIndex, g, f)

Adds a node to the heap.

Public
BinaryHeap (capacity)

Create a new heap with the specified initial capacity.

Public
Clear (pathNodes)

Removes all elements from the heap.

Public
Dispose ()
Public
Rebuild (nodes)

Rebuilds the heap by trickeling down all items.

Public
Remove (nodes, g, f)

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

Public

Public Static Methods

Add (binaryHeap, nodes, pathNodeIndex, g, f)
Public Static
DecreaseKey (heap, nodes, node, index)
Public Static
Expand (heap)

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

Public Static
Remove (nodes, binaryHeap, removedG, removedF)
Public Static
RoundUpToNextMultipleMod1 (v)

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

Public Static
Validate (nodes, binaryHeap)
Public Static

Public Variables

isEmpty

True if the heap does not contain any elements.

Public
numberOfItems

Number of items in the tree.

Public

Public Static Variables

D

Number of children of each node in the tree.

Public Static
GrowthFactor

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

Public Static
NotInHeap
Public Static
SortGScores

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

Public Static

Private/Protected Members

GetF (heapIndex)
Internal
GetG (heapIndex)
Internal
GetPathNodeIndex (heapIndex)
Internal
SetH (heapIndex, h)
Internal
heap

Internal backing array for the heap.

Private