Module jumper.core.bheap
A light implementation of `binary heaps`.
While running a search, some algorithms have to maintains a list of nodes called __open list__. Finding in this list the lowest cost node from the node being processed can be quite slow, (as it requires to skim through the collection of nodes stored in this list) especially when dozens of nodes are being processed (large maps).
The current module implements a binary heap data structure, from which the internal open list will be instantiated. As such, looking up for lower-cost node will run faster, and globally makes the search algorithm run faster.
This module should normally not be used explicitely. The algorithm uses it internally.
Info:
- Copyright: 2012-2013
- License: MIT
- Author: Roland Yonaba
Functions
| 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. |
Tables
| heap | The `heap` class |
Functions
- heap:empty ()
-
Checks if a `heap` is empty
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)
- heap:push (item)
-
Adds a new item in the `heap`
Parameters:
- item object a new object to be queued in the heap
- heap:pop ()
-
Pops from the `heap`.
Removes and returns the lowest cost item (with respect to the comparison function used) from the `heap`.
Returns:
-
object
an object stored in the heap
- heap:heapify ([item])
-
Restores the `heap` property.
Reorders the `heap` with respect to the comparison function being used.
When given arg `item`, will sort that very item in the `heap`.
Otherwise, the whole `heap` will be sorted.
Parameters:
- item object the modified object (optional)