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 self (the calling heap itself, can be chained)
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 self (the calling heap itself, can be chained)
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:

    heap self (the calling heap itself, can be chained)
generated by LDoc 1.2