Module core.bheap
A light implementation of Binary heaps data structure.
While running a search, some search algorithms (Astar, Dijkstra, Jump Point Search) have to maintains a list of nodes called open list. Retrieve from this list the lowest cost node can be quite slow, as it normally requires to skim through the full set of nodes stored in this list. This becomes a real problem especially when dozens of nodes are being processed (on large maps).
The current module implements a binary heap data structure, from which the search algorithm will instantiate an open list, and cache the nodes being examined during a search. As such, retrieving the lower-cost node is faster and globally makes the search end up quickly.
This module is internally used by the library on purpose. It should normally not be used explicitely, yet it remains fully accessible.
Class heap
heap:empty () | Checks if a heap is empty |
heap:clear () | Clears the heap (removes all items queued in the heap) |
heap:push (item) | Adds a new item in the heap |
heap:pop () | Pops from the heap . |
heap:heapify ( [item]) | Restores the heap property. |
Class heap
The heap class.This class is callable. Therefore,
heap(...)
is used to instantiate new heaps.
- heap:empty ()
-
Checks if a heap is empty
Usage:
if myHeap:empty() then print('Heap is empty!') end
Returns:
-
bool
true of no item is queued in the heap, false otherwise
- heap:clear ()
-
Clears the heap (removes all items queued in the heap)
Usage:
myHeap:clear()
Returns:
- heap:push (item)
-
Adds a new item in the heap
Parameters:
- item value a new value to be queued in the heap
Usage:
myHeap:push(1) -- or, with chaining myHeap:push(1):push(2):push(4)
Returns:
- heap:pop ()
-
Pops from the heap .
Removes and returns the lowest cost item (with respect to the comparison function being used) from the heap .
Usage:
while not myHeap:empty() do local lowestValue = myHeap:pop() ... end
Returns:
-
value
a value previously pushed into the heap
- heap:heapify ( [item])
-
Restores the heap property.
Reorders the heap with respect to the comparison function being used.
When given argument item (a value existing in the heap ), will sort from that very item in the heap .
Otherwise, the whole heap will be cheacked.
Parameters:
- item value the modified value
Usage:
myHeap:heapify()
Returns: