Binary heap implementation.
More...
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
|
bool | isEmpty [get] |
| True if the heap does not contain any elements. More...
|
|
|
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...
|
|
◆ BinaryHeap()
Create a new heap with the specified initial capacity.
◆ Add()
◆ Clear()
Removes all elements from the heap.
◆ DecreaseKey()
void DecreaseKey |
( |
Tuple |
node, |
|
|
ushort |
index |
|
) |
| |
|
private |
◆ Expand()
Expands to a larger backing array when the current one is too small.
◆ GetNode()
◆ Rebuild()
Rebuilds the heap by trickeling down all items.
Usually called after the hTarget on a path has been changed
◆ 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()
◆ growthFactor
The tree will grow by at least this factor every time it is expanded.
◆ heap
Internal backing array for the heap.
◆ NotInHeap
const ushort NotInHeap = 0xFFFF |
◆ 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).
◆ isEmpty
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