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.

See

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

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

Inner Types

HeapNode

Item in the heap.

Public Methods

Add (..., nodes, pathNodeIndex, g, h, ...)

BinaryHeap (capacity)

Create a new heap with the specified initial capacity.

Clear (pathNodes)

Removes all elements from the heap.

Dispose ()
GetF (heapIndex)
GetH (heapIndex)
GetPathNodeIndex (heapIndex)
Rebuild (nodes)

Rebuilds the heap by trickeling down all items.

Remove (nodes, ...)

SetH (heapIndex, h)

Replaces the H score of a node in the heap.

Public Static Methods

DecreaseKey (heap, nodes, node, index)
Expand (heap)

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

RoundUpToNextMultipleMod1 (v)

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

Validate (nodes, binaryHeap)

Public Variables

insertionOrder
Public
isEmpty

True if the heap does not contain any elements.

Public
numberOfItems

Number of items in the tree.

Public
tieBreaking

Ties between elements that have the same F score can be broken by the H score or by insertion order.

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

Public Enums

TieBreaking
Public

Private/Protected Members

heap

Internal backing array for the heap.

Private